康托展开式与其逆运算的实现

康托展开式与其逆运算的实现

【C++头algorithm函数next_permutation全排列函数传送门】
【康托展开百度百科传送门】

康托展开式，就是将一个全排列序列唯一地映射到一个整数上的一种公式

以上式的长度为3的全排列序列为例

X = a1*2! + a2*1! + a3*0!

确定 a1, a2, a3，即可确定映射后的值，假设当前排列为 2 3 1

ai的值是当前全排列序列的【第i个数开始到结尾】这一子序列中，第i个数的排位（即：比第i个数小的数的数目）

a1：2 在序列[2, 3, 1]中，有 1 个数比2小，a1=1
a2：3 在序列[3, 1]中，有 1 个数比3小，a2=1
a3：1 在序列[1]中，有 0 个数比1小，a3=0

所以映射后的值为

X = a1*2! + a2*1! + a3*0!
X = 1 *2! + 1 *1! + 0 *0! = 3

代码

#include <iostream>
#include <algorithm>

using namespace std;

#define MAXLEN 114
int a[MAXLEN];
int n;

/*
param index : 要查询的起始下标
return 		: index~n-1下标中a[index]排位 
*/
int find(int index)
{
	int cnt = 0;
	for(int i=index+1; i<n; i++)
	{
		if(a[i] < a[index])
		{
			cnt += 1;
		}
	}
	return cnt;
}

/*
param x ：欲计算的数
return  : x的阶乘  
*/
int fac(int x)
{
	int t = 1;
	for(int i=2; i<=x; i++)
	{
		t *= i;
	}
	return t;
}

int main()
{
	cin>>n;
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	cout<<endl;
	sort(a, a+n);
	do
	{
		for(int i=0; i<n; i++)
		{
			cout<<a[i]<<" ";
		}
		int sum = 0;
		for(int i=0; i<n; i++)
		{
			sum += find(i) * fac(n-1-i);
		}
		cout<<"映射后数值："<<sum<<endl;
		
	}while(next_permutation(a, a+n));

	return 0;
}

康托展开逆运算

一.
根据：X = a1*2! + a2*1! + a3*0! 可以先求取a1, a2, a3

假设现在的编号X=3，计算步骤如下：

X = 3
a1 = X/2! = 1	X = X%2! = 1
a2 = X/1! = 1	X = X%1! = 0
a3 = 0/0! = 0

求得 a1=1, a2=1, a3=0

二.
根据ai求对应排列中的元素

• 设置访问数组visited[]
• 因为输入的排列数组会被排序，在排序后的数组中，找到第ai+1个未被访问的数，这个数就是全排列中这一项的值

排序后序列为[1, 2, 3]
可访问元素为[1, 2, 3]，找到第1+1=2个未被访问的数为2
可访问元素为[1, 3]，找到第1+1=2个未被访问的数为3
可访问元素为[1]，找到第1+0=1个未被访问的数为1

所以X=3对应的序列为[2, 3, 1]

代码

#include <iostream>
#include <algorithm>

using namespace std;

/*
param x ：欲计算的数
return  : x的阶乘  
*/
int fac(int x)
{
	int t = 1;
	for(int i=2; i<=x; i++)
	{
		t *= i;
	}
	return t;
}

int main()
{
	int n;
	int a[114];
	cin>>n;
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	sort(a, a+n);
	
	for(int i=0; i<fac(n); i++)
	{
		cout<<"X="<<i<<" 逆运算求排列式为：";
		int x = i;
		int visited[10] = {0};
		for(int j=n-1; j>=0; j--)
		{
			int ai = x/fac(j);
			x %= fac(j);
			// 找第ai+1个未被访问的数字 
			int index = -1;
			while(ai+1)
			{
				index += 1;
				if(visited[index] == 0)
				{
					ai -= 1;
				}
			}
			// 访问并输出 
			visited[index] = 1;
			cout<<a[index]<<" ";
		}
		cout<<endl;
	}

	return 0;
}