康托排列

或称康托展开

X=a[n-1]*(n-1)!+...+a[2]*2!+a[1]*1!

其中，a为整数，并且0<=a<i,i=1,2,..,n

它构成一个全排列到一个整数的双射。

例：

{1,2,3,4,...,n}表示1,2,3,...,n的排列如

{1,2,3}

按从小到大排列一共6个

123

132

213

231

312

321

代表的数字

1

2

3

4

5

6

也就是把10进制数与一个排列对应起来。他们间的对应关系可由康托展开来找到。

如我想知道321是{1,2,3}中第几个大的数可以这样考虑

第一位是3，当第一位的数小于3时，那排列数小于321

如

123

213

小于3的数有1，2

所以有2*2!个

再看小于第二位2的

小于2的数只有一个就是1

所以有1*1!=1

所以小于321的{1,2,3}排列数有2*2!+1*1!=5个所以321是第6个大的数。

2*2!+1*1!是康托展开

再举个例子

1324是{1,2,3,4}排列数中第几个大的数

第一位是1小于1的数没有，是0个

0*3!

第二位是3小于3的数有1，2但1已经在第一位了所以只有一个数2

1*2!

第三位是2小于2的数是1，但1在第一位所以有0个数

0*1!

所以比1324小的排列有0*3!+1*2!+0*1!=2个

1324是第三个大数。

英文介绍：

Every nonnegative integer less than n! has a unique Cantor expansion

all! + a22! + ... + an-1(n - 1)!

where ai is a nonnegative integer not exceeding i, for i = 1, 2, . . . , n 1. The integers al, a2, . . . , an-1 are called the Cantor digits of this integer.

Given a permutation of {l, 2, ... , n}, let ak-1, k = 2, 3, . . . , n, be the number of integers less than k that follow k in the permutation. For instance, in the permutation 43215, al is the number of integers less than 2 that follow 2, so that al = 1. Similarly, for this example a2 = 2, a3 = 3, and a4 = 0. The number associated with this permutation will thus be: 1x1! + 2x2! + 3x3! = 23. Consider the function from the set of permutations {l, 2, 3, ... , n} to the set of nonnegative integers less than n! that sends a permutation to the integer that has al, a2, ... , an-1, defined in this way, as its Cantor digits.

This is actually a bijection f: P¬n  {0, …, n! – 1}.

To find the permutation   P8 such that f() = 2001 we proceed as follows:

a. Find the Cantor digits of : 2001 = 2*6! + 4*5! + 3*4! + 1*3! + 1*2! + 1*1!

b. Construct the permutation by inserting 8, then 7 and so on.

 = 8}

7 * * 8} (a6 = 2, two numbers < 7 come after 7)

6 * * 7 * * 8} (a5 = 4, four numbers < 6 come after 6)

6 5 * 7 * * 8} (a4 = 3, three numbers < 5 come after 5)

6 5 * 7 4 * 8} (a3 = 1, one number < 4 comes after 4)

6 5 3 7 4 * 8} (a2 = 1, one number < 3 comes after 3)

2 6 5 3 7 4 * 8} (a1 = 1, one number < 2 comes after 2)

 = {2 6 5 3 7 4 1 8}

Comment: The algorithm for finding the Cantor digits of an integer n is a “Greedy” algorithm.