自学康托展开（做8数码问题）去网上查资料，无无一明白，又苦于资料太少，讲的太含蓄
然而《周易》云：天行健，君子以自强不息
于是奋战6h作此文
为像我一样的菜扫清前行障碍，故名曰：“详解”
如有不当之处，恳请指正
~_~_~_~_~_~_~_华丽的分割线_~_~_~_~_~
康托展开(x)的实际意义:对于一个长度为n的数列包含元素[0..n-1]
x表示此数列是{0,1,2…n-1}全排列中第几小的。最小的为0
(但是通常应用的康托展开有时是[1..n])
例如当n=3时(默认[1..n]):
{1,2,3}x=0;{1,3,2}x=1;
{2,1,3}x=2;{2,3,1}x=3;
{3,1,2}x=4;{3,2,1}x=5;
(针对0..n-1是连续自然数 )
其计算方法:
\(
X=a[n]\times (n-1)!+a[n-1]\times (n-2)!+…a[i]\times (i-1)!a[2]\times 1!+a[1]\times 0! \\
\)
X=a[n]*(n-1)!+a[n-1]*(n-2)!+…a[i]*(i-1)!+a[2]*1!+a[1]*0!;
或(d对于第一位为a[1],下面代码即是如此):
\(
X=a[1]\times (n-1)!+a[2]\times [n-2]!+…+a[n-1]\times 1!+a[n]\times 0! \\
\)
X=a[1]*(n-1)!+a[2]*[n-2]!+…+a[n-1]*1!+a[n]*0！
其中a[i]表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小
核心代码：
|
1 2 3 4 5 6 7 |
readln(n); for i:=1 to n do read(arr[i]); for i:=1 to n-1 do begin //循环当前位 t=0;//代表第几大 for j=i+1 to n if arr[j] ans:=ans+t*fac[n-i-1];//fac[i]表示i阶乘 end; writeln(ans) ; |
实际代码（C实现）个人认为比较详细了，如果有不理解，切记看完上面说明
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <stdio.h> int fac[101],arr[101]; int ten[11]={0,1,2,3,4,5,6,7,8,9,10};//全排列元素序列,此处是[1..10] int n,e; /* 康托展开(x)的实际意义:对于一个长度为n的数列包含元素[0..n-1] x表示此数列是{0,1,2...n-1}全排列中第几小的。最小的为0 (但是通常应用的康托展开有时是[1..n]) 例如当n=3时(默认[1..n]): {1,2,3}x=0;{1,3,2}x=1; {2,1,3}x=2;{2,3,1}x=3; {3,1,2}x=4;{3,2,1}x=5; (针对0..n-1是连续自然数 ) 其计算方法: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...a[i]*(i-1)!a[2]*1!+a[1]*0!; 或(d对于第一位为a[1],下面代码即是如此): X=a[1]*(n-1)!+a[2]*[n-2]!+...+a[n-1]*1!+a[n]*0！ 其中a[i]表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小 Code: readln(n); for i:=1 to n do read(arr[i]); for i:=1 to n-1 do begin //循环当前位 t=0;//代表第几大 for j=i+1 to n if arr[j]<arr[i] inc(t); ans:=ans+t*fac[n-i-1];//fac[i]表示i！ end; writeln(ans) ; */ int cantor(int k){//康托展开,此展开与序列元素大小无关,仅与大小排列顺序有关,{0,1,2}=0；{1,2,3}=0； int i,j,t,ans=0; for (i=1;i<n;i++){ /* 对于循环到n-1的解释： 循环到n无意义(0*0!恒等于0),且 ans=(ans+t)*(n-i);不允许i=n,其本质原因是0!=1而不是0 */ t=0; for (j=i+1;j<=n;j++) if (arr[j]<arr[i]) t++; //其中t表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小 ans=(ans+t)*(n-i);//简便算法,解释见下 /* 此处代码本应为(二者等价,可相互替换): ans+=t*fac[n-i]; 对于 ans=(ans+t)*(n-i); 我们可以这样理解: 当i=1时,ans为0,最终结果应使t*(n-1)!=t*(n-1)*(n-2)*...*1; 当i=n时 */ } return(ans) ; } int uncantor(int x,int k){//逆康托展开,x表示康托展开 int i,j,l,t,u[12]; memset(&u,0,sizeof(u)); for (i=1;i<=k;i++){//枚举各位 t=x/fac[k-i];//t：比当前位小的只有t个 x-=t*fac[k-i];//删去 for (j=1,l=0;l<=t;j++)if (u[j]==0)l++;//此处l<=t并不正确理应是l<t,故j多取了1； /* for(j=1,l=0;l<t;j++) 不能处理常见的t=0的情况,若t=0则会造成不执行循环 故在下方做一减法 */ j--; u[j]=1; arr[i]=j;//这里默认是集合元素为[1..n] //若有必要,改为arr[i]=ten[j]; } } int main(){ int i,j; fac[0]=1; for (i=1;i<=12;i++)fac[i]=fac[i-1]*i;//计算阶乘 scanf("%d",&n); for (i=1;i<=n;i++){ scanf("%d",&arr[i]); } printf("%d\n",e=cantor(n)) ; memset(&arr,0,sizeof(arr)); uncantor(e,n); for (i=1;i<=n;i++)printf("%3d",arr[i]); getch(); } |
需要注意的（其实代码中注释很清楚）
0！=1
康托展开只与数列元素个数和其大小排列顺序有关（即第几大的元素排在第几位）
需要康托展开的数列不允许有重复
谢谢博主，那个尼康托展开给了我莫大的帮助