以下为个人理解, 建议参考博客地址:http://www.cnblogs.com/1-2-3/archive/2011/04/17/generate-permutation-part1.html
康托展开为一个排列赋予相应的值,并可以由这个值得到对应的排列。比如1~6一共有6! = 720种排列组合,按照字典序给每一种排序有小到大给一个ID值。如: 1 2 3 4 5 6 ID为1, 1 2 3 4 6 5 ID为2, 6 5 4 3 2 1 ID为720.
如果一个排列为 4 5 3 2 1 6, 那么拍在他前面的排列有多少种呢?
如果第一位为1, 那么后面五位数可以排成 5! = 120种,同理,第一位为2, 3, 也分别有120种。。。。。可以得到,第一位比他小的种类有 3* 5! = 360种。
如果第一位确定是4, 而第二位分别为1, 2, 3 (4在第一位已确定不会再出现不用再考虑)分别有4!=24种, 可以得到,第一位确定第二位比他小的有3 * 4! = 72种。
................................................................. 可以得到,前两位确定第三位比他小的有2 * 3! = 12种。
三 四 有1 * 2! = 2种。
四 五 有0 * 1! = 0种。
五 六 有 0*0! = 0种。
如果最小值为1, 那么 4 5 3 2 1 6 的ID为1 + 360 + 72 + 12 + 2 +0 + 0 = 447;
由上可知,ID = A[1] * (n-1)! + A[2] * (n-2)! + ... + A[n]*(n-n)!. 这个就是康托展开公式。其中A[i] 为到目前为止剩下的数内第A[i]大的数字(例: 第一位确定分别为2和3, 那么在确定第三位的时候第二大的就是4)。
下一个问题就是康拓逆展开,给定一个ID,找出这个ID对应的排列。
将上面步骤倒过来。例如,447。
447 -1 = 446;
446 / (5!) = 3, 446 % (5!) = 86;
86 / (4!) = 3,86 %(4!) = 14;
14 / (3!) = 2, 14%(3!) = 2;
2 / (2!) = 1, 2 % (2!) = 0;
0 / (1!) = 0, 0 % 1 = 0;
推得4 5 3 2 1 6.
由康托展开可以得到下一个排列,c++种next_permutation函数可以直接实现下一个排列功能,也可以用康托展开自己实现。
代码如下(注释代码是我懒得删的。。。)
#include <iostream> #include <algorithm> using namespace std; /* int GetJ(int n) { int c = 1; for(int i = 1; i <= n; i++) c *= i; return c; } ///排列组合算法之康托展开 ///s = A[1] * (n-1)! + A[2] * (n-2)! + ... + A[n] * (n-n)! int main() { int n; while(cin >> n) { long long Ti = 0; int m = GetJ(n); for(int i = 1; i <= m; i++) { int k = i-1; int A[25]; ///有序数列 int B[25] = {0}; ///是否已经出现过 ///得到A[] for(int j = n - 1; j >= 0; j--) { A[n-j] = k / GetJ(j); k %= GetJ(j);Ti++; } ///由A[]得到数列 for(int j = 1; j <= n; j++) { int i2 = A[j] + 1;///当前数字中排列在第i2个的数字 int j2 = 0; for(int k = 1; k <= n; k++) { Ti++; if(!B[k]) {j2++;} if(j2 == i2) { B[k] = 1; cout << k << " "; break; } } } cout << endl; } cout << Ti << endl; } } */ int * Fun(int A[], int num) { int ima = num-1; int jma = num-1; for(int i = num - 1; i >= 0; i--) { if(A[i] > A[ima]) ima = i; if(A[i] < A[ima]) {jma = i;break;} } swap(A[ima], A[jma]); if(ima == jma) return NULL; return A; } int *Fun2(int A[], int num) { int ok = 0; for(int i = num - 1; i >= 0; i--) { if(i < num - 1 && A[i] < A[i+1]) { ok = 1; int k = num-1; for(int j = i + 1; j < num; j++) { if(A[j] > A[i]) { k = (A[k] < A[j] ? k : j); if(A[k] < A[i]) k = j; } } swap(A[i], A[k]); sort(A + i + 1, A + num); return A; } } if(!ok) return NULL; return A; } int main() { int A[20]; int n; /*while(cin >> n) { for(int i = 0; i < n; i++) { cin >> A[i]; } Fun(A, n); for(int i = 0; i < n; i++) { cout << A[i] << " "; } cout << endl; }*/ while(cin >> n) { for(int i = 0; i < n; i++) A[i] = i; int Ti = 0; do { Ti++; for(int i = 0; i < n; i++) { //cout << A[i] << " "; } //cout << endl; }while(Fun2(A, n)); cout << "Ti = " << Ti << endl; } return 0; }