词条 | 康托排列 |
释义 | 或称康托展开 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. |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。