于康托展开"/>
关于康托展开
以下定义援引自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;
}
更多推荐
关于康托展开
发布评论