康托展开详解

自学康托展开(做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]小
核心代码:

实际代码(C实现)个人认为比较详细了,如果有不理解,切记看完上面说明

需要注意的(其实代码中注释很清楚)

0!=1

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

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

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

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

1 Response

发表评论