对于求一个全排列的问题，我们不可能一下子列出所有排列的情况（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]); }}
