关于康托展开

于康托展开"/>

关于康托展开

以下定义援引自wiki百科：

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

康托展开的公式：

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

其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。

例如：

一个排列：3 4 6 5 1 2 7

则计算公式为：2 * 6 ! + 2 * 5 ! + 3 * 4 ! + 2 * 3 ! + 0 * 2 ! + 0 * 1 ! + 0 * 0 !

其中2 * 6 !中的2表示，比3小的数有两个，以这样的数开始的排列有6!个，因此第一项为2*6! 

其中2 * 5 !中的2表示，比4小的数有三个，前面已经有一个3了，故而一共有2个比四小的数可以在第二位出现（如 3 1 .......和 3 2 ......），而以这样的数开始的排列有5!个，因此第一项为2*5!

/**康托展开 *Author:Xu.Jin*Date:2013/3/25*本程序用来计算康托展开的顺序，利用了如下公式公式：*                    *      X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!**Example:**请输入n位全排列中的正整数n：7*请输入n位全排列：3 4 6 5 1 2 7*上述排列在全排列中的顺序是：第1764**/package com.xujin;import java.util.Scanner;public class Cantor {public static void main(String...args){Cantor cantor = new Cantor();while(true){cantor.input();System.out.println("上述排列在全排列中的顺序是：第" + cantor.claCantor());}}//输入private void input(){System.out.print("请输入n位全排列中的正整数n：");number = cin.nextInt();System.out.print("请输入n位全排列：");permutation = new int[number];for(int i = 0; i< number; i++){permutation[i] = cin.nextInt();}}//计算康托展开private int claCantor(){int result = 0;for(int i = number - 1; i >= 0 ; i--){result += fac(i) * modulus(number - 1- i, permutation);}return result;}//阶乘private int fac(int n){int res = 1;for(int i = n; i >= 1; i--){res *= i;}return res;}//公式前面的系数a[i]private int modulus(int index, int[] per){int count = per[index] - 1;for(int i = 0; i < index; i++){if(per[i] < per[index]) count--;}//System.out.println(count);return count;}Scanner cin = new Scanner(System.in);private int number;private int[] permutation;
}