康托展開的公式是：X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，ai為當前未出現(xiàn)的元素中是排在第幾個（從0開始）。
　? 例如，有一個數(shù)組 s = ["A", "B", "C", "D"]，它的一個排列 s1 = ["D", "B", "A", "C"]，現(xiàn)在要把 s1 映射成 X。n 指的是數(shù)組的長度，也就是4，所以
X(s1) = a4*3! + a3*2! + a2*1! + a1*0!
關(guān)鍵問題是 a4、a3、a2 和 a1 等于啥？
a4 = "D" 這個元素在子數(shù)組 ["D", "B", "A", "C"] 中是第幾大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，"D"是第3大的元素，所以 a4 = 3。
a3 = "B" 這個元素在子數(shù)組 ["B", "A", "C"] 中是第幾大的元素。"A"是第0大的元素，"B"是第1大的元素，"C" 是第2大的元素，所以 a3 = 1。
a2 = "A" 這個元素在子數(shù)組 ["A", "C"] 中是第幾大的元素。"A"是第0大的元素，"C"是第1大的元素，所以 a2 = 0。
a1 = "C" 這個元素在子數(shù)組 ["C"] 中是第幾大的元素。"C" 是第0大的元素，所以 a1 = 0。（因為子數(shù)組只有1個元素，所以a1總是為0）
所以，X(s1) = 3*3! + 1*2! + 0*1! + 0*0! = 20

通過康托逆展開生成全排列
　　如果已知 s = ["A", "B", "C", "D"]，X(s1) = 20，能否推出 s1 = ["D", "B", "A", "C"] 呢？
　　因為已知 X(s1) = a4*3! + a3*2! + a2*1! + a1*0! = 20，所以問題變成由 20 能否唯一地映射出一組 a4、a3、a2、a1？如果不考慮 ai 的取值范圍，有
3*3! + 1*2! + 0*1! + 0*0! = 20
2*3! + 4*2! + 0*1! + 0*0! = 20
1*3! + 7*2! + 0*1! + 0*0! = 20
0*3! + 10*2! + 0*1! + 0*0! = 20
0*3! + 0*2! + 20*1! + 0*0! = 20
等等。但是滿足 0 <= ai <= n-1 的只有第一組。可以使用輾轉(zhuǎn)相除的方法得到 ai，如下圖所示：

知道了a4、a3、a2、a1的值，就可以知道s1[0] 是子數(shù)組["A", "B", "C", "D"]中第3大的元素 "D"，s1[1] 是子數(shù)組 ["A", "B", "C"] 中第1大的元素"B"，s1[2] 是子數(shù)組 ["A", "C"] 中第0大的元素"A"，s[3] 是子數(shù)組 ["C"] 中第0大的元素"C"，所以s1 = ["D", "B", "A", "C"]。

c++代碼如下：

#include<cstdio> #include<cstring> const int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320,362880};///階乘 int n; bool vis[10]; void invKT(int k) { //輸出第k個全排列 int i, j, t; memset(vis, 0, sizeof(vis)); for (i = 0; i < n; i++) { t = k / fac[n - i - 1]; //查找第t大的元素 for (j = 1; j <= n; j++) if (!vis[j]) { if (t == 0) break; t--; } char ch=j+48; //輸出字符格式，減少占用的空間 printf("%c ", ch); vis[j] = true; k %= fac[n - i - 1];///余數(shù) } } int main() { scanf("%d",&n);int m=1;for(int i=1;i<=n;i++) m=m*i;for(int k=0;k<m;k++){invKT(k); printf("\n");} }

提交codevs1294（http://codevs.cn/problem/1294/）沒有發(fā)現(xiàn)明顯優(yōu)勢：

從1294看程序的使用空間（特別是第5個點）：
康托展開式：

?

普通全排列算法：

? ? ? ?

附普通全排列的代碼：

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int a[100],p[100] ; int n; int main(){cin>>n;for (int i=1;i<=n;i++) {a[i]=i;cout<<i<<" ";}//初值為最小的字母表順序cout<<endl;while (next_permutation(a+1,a+n+1)){for (int i=1;i<n;i++) printf("%d ",a[i]);printf("%d\n",a[n]);}return 0; }

?說明：除了程序代碼，大部分文字來源于：https://www.cnblogs.com/1-2-3/archive/2011/04/25/generate-permutation-part2.html

轉(zhuǎn)載于:https://www.cnblogs.com/ssfzmfy/p/8267036.html

總結(jié)

以上是生活随笔為你收集整理的通过康托逆展开生成全排列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。