一、康托展开运算

把一个整数X展开成如下形式：
X = a_n * (n - 1)! + a_n-1 * (n - 2)! + ... + a_i * (i - 1)! + ... + a₂ * 1! + a₁ * 0!
其中，a_i为整数，并且0 <= a_i < i，1 <= i <= n)。
a_i表示原数的第i位在当前未出现的元素中是排在第几个。

康托展开的最基本应用就是求一个排列（按字典序）的序号（即第几个）。而其逆运算就是求序号对应的排列。

二、例子

例1：n = 3时，即三位数字的全排列，321的序号是多少？

方法一：
1 2 3这三个数按字典序来进行排列，得：

123
132
213
213
312
321

这里可以看出321是第6个数。

方法二：
321的第一位是3，则第一位小于3的数一定排在321的后面，这样的排列有22！个。
321的第二位是2，则第一位等于3第二位小于2的数一定排在321的后面，这样的排列有11!个。
321的第三位是1，则第一位为3第二位为2第3位小于1的数一定排在321的后面，这样的排列有0个。
所以排在321前面的数有2 * 2! + 1 * 1! = 5个。321是第5 + 1 = 6个数。

例2：对于n = 3的全排列，第6个数是多少？

分析：
现将序号减去1，为5。
5/2！=2余1，说明比第一位数小的数有2个，那么第一位肯定为3。
上一步的余数/1! = 1/1!=1余0，说明比第二位小的数有1个，那么第二位肯定是2。
第三为只能为1了。
所以第6个数是321。

例3：n = 4的全排列中，1324是第几个数？

1324的第一位是1，小于1的数有0个，所以总共有 0 * 3! = 0个。
1324的第二位是3，小于3的数有1和2，但1已经在第一位了，所以只有一个数2。再考虑第三位和第四位的排列数为2!，所以共有 12! = 2个。
1324的第三位是2，小于2的数是1，但1已经排在第一位了，所以有0个数 。 01! = 0。 所以比1324小的排列有0 * 3! + 1 * 2! + 0 * 1! = 2个。
综上，1324是的序号为2 + 1 = 3。

例4：对于n = 6的全排列，153426的序号是多少？再往后数200个，得到的数是多少？

①
153426的第一位数是1，比1小的数有0个，共有0 * 5！= 0个。
153426的第二位数是5，比5小的数有4个，但是1已经出现在首位了，所以只有2，3，4这三个。共有3 * 4！= 72个。
153426的第三位数是3，比3小的数有2个，但是1已经出现在首位了，所以只有2这1个。共有1 * 3！= 6个。
153426的第四位数是4，比4小的数有3个，但是1和3已经出现在首位和第三位了，所以只有2这1个。共有1 * 2！= 2个。
153426的第五位数是2，比2小的数有1个，但是1已经出现在首位了，所以共有0 * 1！= 0个。
153426的第六位数是6，比6小的数有5个，但是这5个数已经被前五位数占了，所以共有0 * 0！= 0个。
综上，153426排在第72 + 6 + 2 + 1 = 81个。

②
第81个再往后数200个，就是第281个。
首先将281减去1，即280。
第一位为280 / 5! = 2余40，说明比第一位数小的数有2个，则第一位数必为3
上一步的余数 / 4! = 40 / 4! = 1余16，说明比第二位数小的数有1个，第二位数必为2。
上一步的余数 / 3! = 16 / 3！= 2余4，说明比第三位数小的数有2个。在前两位数是3和2的前提下，第三位只能为5，这样比它小的两个数为1或4。
上一步的余数为 4/ 2! = 2余0 ，说明比第四位数小的数有2个。因为前三位数分别为3、2、5，则第四位数必为6。
上一步的余数为 0/1! = 0余0 ，说明比第五位数小的数有0个，则第五位数必为1。
剩下一位数为4。
综上，153426往后数的第200个数是325614。

了解小朋友学编程请加微信307591841 或QQ群581357582
关注公众号请扫描二维码

qrcode_for_kidscode_258.jpg