康托展开和逆康托展开

康托展开就是一种特殊的哈希函数。

公式：

X = a_n*(n-1)! + a_n-1*(n-2)! + …… + a_i*(i-1)! + …… + a₂*(1)! + a₁*(0)!

其中，a[i] 为当前未出现的元素中，它排在第几个（从0开始计数）。 //不理解无妨，继续往后看样例。

例如，有一个数组 S=[A,B,C,D]。可以对它生成一个全排列:

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

一共是24个…接下来：我们取出其中一个全排列。DBAC，请问，它在所有全排列中，是第几个？

首先我们不按康托公式来计算：好吧，首先列出所有的全排列。24个（0-23）。请注意这个编号，0-23…

然后开始数 DBAC位于第21个…编号是20…（如果学习过全排列，应该知道做出这样一个全排列…有多慢！）

接下来，根据康托公式：n=4，那么 a[4],a[3],a[2],a[1]的值分别是多少呢。

a[4]的值为，在[DBAC]这个数组中，第一个元素，它在没有出现过的元素内，是第几大。（同样从0开始计数）。

DBAC->3102… 所以D在这个数组中，是第3大的元素。a[4]=3

同理，a[3]的值为在[DBAC]这个数组中，第二个元素，它在没有出现过的元素内，是第几大。（注意，这里D已经出现过，不再计入）

所以 DBAC->0102 请注意D已经出现过，所以不在计数范围。所以a[3]=1

a[2]的值为在[DBAC]这个数组中，第三个元素，它在所有没有出现过的元素内，是第几大。（这里，DB都已经出现过，不统计）

所以DBAC->0001 ,a[2]=0;

a[1] = 0 因为只有一个元素了…

代入公式计算得到 X=3*(3!) + 1*(2)! + 0*(1)! + 0*(0)! = 3*3*2+1*2 = 20

以上是康托展开的运算方法。

代码如下：

#include <iostream>
#include <string>
using namespace std;

int JC[20] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };

int Cantor(string A)
{
	int result = 0;
	int n=A.length();
	
	for(int i=0;i<n;i++)
	{
		int temp = 0;
		for(int j=i+1;j<n;j++)
		{
			if(A[i]>A[j])
				temp ++;
		}
		result += (temp*JC[n-i-1]);
	}
	
	return result; 
}

int main()
{
	int T;
	cin >> T;
	for(int case_T = 1 ; case_T<=T;case_T++)
	{
		string A;
		cin >> A;
		cout << "Case " << case_T << ":" << Cantor(A) << endl;
	} 
}

#include <iostream>

#include <string>

using namespace std;

int JC[20] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };

int Cantor(string A)

{

int result = 0;

int n=A.length();

for(int i=0;i<n;i++)

{

int temp = 0;

for(int j=i+1;j<n;j++)

{

if(A[i]>A[j])

temp ++;

}

result += (temp*JC[n-i-1]);

}

return result;

}

int main()

{

int T;

cin >> T;

for(int case_T = 1 ; case_T<=T;case_T++)

{

string A;

cin >> A;

cout << "Case " << case_T << ":" << Cantor(A) << endl;

}

逆康托展开，就是康托展开的逆运算。

已知 X = a_n*(n-1)! + a_n-1*(n-2)! + …… + a_i*(i-1)! + …… + a₂*(1)! + a₁*(0)! = N 和项数n

求数组a[]

例如已知 a[4]*(3!) + a[3]*(2!) + a[2]*(1!) + a[1]*(0!) = 20 ，项数为4，求这个全排列。

计算方法：

20%(3!) = 2 20/(3!) = 3 故a[4]为[ABCD] 中第3个数据为 D.

2%(2!)= 0 2/(2!) =1 故a[3]为[ABC] 中第1个数据为 B.

0%(1!) =0 0/(1!)= 0 故a[2]为[AC] 中第0个数据为 A.

0%(0!)=0 0/(0!)= 0 故a[1]为[C] 中第0个数据为 C.

故数组为 [3,1,0,0]

数据项为 [D,B,A,C]

计算过程就是这样，代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
const int SIZE_N = 20;//0-19

__int64 JC[SIZE_N];

void init()
{
	JC[0] = 0;
	JC[1] = 1;
	for(int i=2;i<SIZE_N;i++)
	{
		JC[i] = JC[i-1]*i;
	}
}

void ReCantor(__int64 N,__int64 M)
{
	int A[SIZE_N];
	for(int i=0;i<N-1;i++)
	{
		A[i]=M/JC[N-i-1];
		M = M%JC[N-i-1];
	}
	A[N-1] = 0;

/* 
	for(int i=0;i<N;i++)
	{
		cout << A[i] << " ";
	}
	cout << endl;
*/

	int S[SIZE_N];
	for(int i=0;i<SIZE_N;i++)
	{
		S[i] = i;
	}
	
	for(int i=0;i<N;i++)
	{
		int temp = A[i];
		A[i] = S[A[i]];
		for(int j=temp;j<N;j++)
		{
			S[j]=S[j+1];
		}
	}
	for(int i=0;i<N;i++)
	{
		printf("%c",'A'+A[i]);
	}
}

int main()
{
	init();
	int T;
	cin >> T;
	for(int case_T = 1;case_T<=T;case_T++)
	{
		__int64 N,M;
		cin >> N >> M;
		cout << "Case " << case_T << ":";
		ReCantor(N,M);
		cout << endl;
	} 
}

#include <iostream>

#include <cstdio>

using namespace std;

const int SIZE_N = 20;//0-19

__int64 JC[SIZE_N];

void init()

{

JC[0] = 0;

JC[1] = 1;

for(int i=2;i<SIZE_N;i++)

{

JC[i] = JC[i-1]*i;

}

void ReCantor(__int64 N,__int64 M)

{

int A[SIZE_N];

for(int i=0;i<N-1;i++)

{

A[i]=M/JC[N-i-1];

M = M%JC[N-i-1];

}

A[N-1] = 0;

for(int i=0;i<N;i++)

{

cout << A[i] << " ";

}

cout << endl;

int S[SIZE_N];

for(int i=0;i<SIZE_N;i++)

{

S[i] = i;

}

for(int i=0;i<N;i++)

{

int temp = A[i];

A[i] = S[A[i]];

for(int j=temp;j<N;j++)

{

S[j]=S[j+1];

}

for(int i=0;i<N;i++)

{

printf("%c",'A'+A[i]);

}

int main()

{

init();

int T;

cin >> T;

for(int case_T = 1;case_T<=T;case_T++)

{

__int64 N,M;

cin >> N >> M;

cout << "Case " << case_T << ":";

ReCantor(N,M);

cout << endl;

}

康托展开和逆康托展开

Tagged on: Algorithm Math