首页 > 数学相关 > 数论应用 > 康托展开式-C++
2014
01-08

康托展开式-C++

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

以下称第x个全排列是都是指由小到大的顺序。

公式

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。

a[i]的意义参见举例中的解释部分

举例

例如,3 5 7 4 1 2 9 6 8 展开为 98884。因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解释:

排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!

排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!

以此类推,直至0*0!

用途

显然,n位(0~n-1)全排列后,其康托展开唯一且最大约为n!,因此可以由更小的空间来储存这些排列。由公式可将X逆推出对应的全排列。

康托展开的逆运算

既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出n的全排列中第x大排列。

如n=5,x=96时:

首先用96-1得到95,说明x之前有95个排列.(将此数本身减去!)
用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4.
用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5.
用5去除2!得到2余1,类似地,这一位是3.
用1去除1!得到1余0,这一位是2.
最后一位只能是1.
所以这个数是45321.

按以上方法可以得出通用的算法。

//============================================================================
// Name        : 康托展开式.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
//============================================================================
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

//阶乘
int fac[] = {1,1,2,6,24,120,720,5040,40320};

int kt(int n,int s[]){
	int sum = 0,smallNum;
	for(int i=0; i<n; i++){
		smallNum = 0; //比当前数小的数
		for(int j=i+1; j<n; j++)
			if(s[i] > s[j])
				smallNum++;
		sum += smallNum * fac[n-i-1];
	}
	return sum;
}

void invKT(int n, int k, int s[]){
	int t,j;
	bool visit[10] = {false}; //需要记录该数是否已在前面出现过
	for(int i=0; i<n; i++){
		t = k/fac[n-i-1];
		for(j=1; j<=n; j++){
			if(!visit[j]){
				if(t == 0) break;
				t--;
			}
		}
		s[i] = j;
		visit[j] = true;
		k %= fac[n-i-1];
	}
}

int main() {
	int arr[] = {1,3,2,5,4};
	printf("%d\n", kt(5,arr));

	int desArr[5];
	invKT(5, 7, desArr);

	for(int i=0; i<5; i++)
				cout << desArr[i] << ",";
			cout << endl;
	return 0;
}

 


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的