锐客网

  1. 首页 > it技术 > >

关于全排列算法（支持有重复的数字的情况）

对于求一个全排列的问题，我们不可能一下子列出所有排列的情况（n！种情况），
我们可以从一个已知的排列，来获得下一个排列。对于任意的一个排列，他的下一个排列是什么了？
比如说：453987621，我的想法是：
从该排列的右边向左边遍历，找到第一个比其右边小的数，此处是
3（3<9），然后遍历3右边的数字，找到比他大的最小的数字，此处为6，
将3与6交换，排列变为456987321，最后将6
后面的数字逆序即可，（987321变成123789），所以得到的下一个
排列为456123789。
开始时我们初始化为123456789，最后判断得到987654321的排列，则得到了所有的全排列。
代码如下：


关于全排列算法（支持有重复的数字的情况）
文章图片
#include < iostream >
关于全排列算法（支持有重复的数字的情况）
文章图片
using namespace std;
关于全排列算法（支持有重复的数字的情况）
文章图片
void init( int * a, int n);
关于全排列算法（支持有重复的数字的情况）
文章图片
void _swap( int & i, int & j);
关于全排列算法（支持有重复的数字的情况）
文章图片
void inverse( int * a, int startpos, int n);
关于全排列算法（支持有重复的数字的情况）
文章图片
int main( int )
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
... {
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
int a[100] = ...{0};
关于全排列算法（支持有重复的数字的情况）
文章图片
int n,i,j,k;
关于全排列算法（支持有重复的数字的情况）
文章图片
cout << "请输入全排列的个数(n < 10)" << endl;
关于全排列算法（支持有重复的数字的情况）
文章图片
cin >> n;
关于全排列算法（支持有重复的数字的情况）
文章图片
init(a,n); //初始化为类似于1234...的排列
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
while(1)...{
关于全排列算法（支持有重复的数字的情况）
文章图片
for(i = n - 1; i >= 1; i--)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
if(a[i] < a[i + 1])
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
break;
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
if(i < 1)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
break; //已经遍历完毕了
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
else
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
for(j = i + 1; j <= n; j++)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
if(a[i] >= a[j])//若是1234的情况，j最终为n+1，仍然正确
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
break; //加上"="后则可以解决重复数字排列的问题，如对1134进行的全排列
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
_swap(a[i],a[j - 1]);
关于全排列算法（支持有重复的数字的情况）
文章图片
inverse(a,i + 1,n);
关于全排列算法（支持有重复的数字的情况）
文章图片
for(i = 1; i <= n; i++)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
cout << a[i];
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
cout << endl;
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
return -1;
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
void _swap( int & i, int & j)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
... {
关于全排列算法（支持有重复的数字的情况）
文章图片
int temp;
关于全排列算法（支持有重复的数字的情况）
文章图片
temp = i;
关于全排列算法（支持有重复的数字的情况）
文章图片
i = j;
关于全排列算法（支持有重复的数字的情况）
文章图片
j = temp;
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
void init( int * a, int n)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
... {
关于全排列算法（支持有重复的数字的情况）
文章图片
int i;
关于全排列算法（支持有重复的数字的情况）
文章图片
for(i = 1; i <= n; i++)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
a[i] = i;
关于全排列算法（支持有重复的数字的情况）
文章图片
a[1] =1;
关于全排列算法（支持有重复的数字的情况）
文章图片
a[2] = 1;
关于全排列算法（支持有重复的数字的情况）
文章图片
cout << a[i];
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
cout << endl;
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
void inverse( int * a, int startpos, int n)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
... {
关于全排列算法（支持有重复的数字的情况）
文章图片
int i,mid = (n - startpos+ 1) / 2 ;
关于全排列算法（支持有重复的数字的情况）
文章图片
for(i = 0; i < mid; i++)
关于全排列算法（支持有重复的数字的情况）
文章图片
关于全排列算法（支持有重复的数字的情况）
文章图片
...{
关于全排列算法（支持有重复的数字的情况）
文章图片
_swap(a[startpos + i],a[n - i]);
关于全排列算法（支持有重复的数字的情况）
文章图片
}
关于全排列算法（支持有重复的数字的情况）
文章图片
} 【关于全排列算法（支持有重复的数字的情况）】

    推荐阅读


    上一篇：html相关

    下一篇：Mathematic）|关于循环群中阶数与（生成元及子群）的计算关系（2009年pku最后一道题，无官方明确给出的标准答案）