康托展开详解

Posted by comzyh

自学康托展开（做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

康托展开只与数列元素个数和其大小排列顺序有关（即第几大的元素排在第几位）

需要康托展开的数列不允许有重复

原创文章，转载请注明(最好把图片带走)： 转载自Comzyh的博客

本文链接地址: 康托展开详解

1 Response

为 cccsober 发表评论 取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。