康拓展开与康拓展开的逆

康托展开

康拓展开一般是用于计算一个全排列数字排在所有全排列的大小位置。

那么到底怎么计算呢？

敲重点

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

从第一个数字开始到倒数第二个数字，计算需要计算的那个数字之后比这个数小的数字有几个，再乘以（n-x）！，n是全排列的

数字，x是当前数字的位置。

下面就是代码。

#include<bits/stdc++.h>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//提前预处理阶乘的值
int main()
{
	string a;
	int n,res=0,cnt;
	cin>>n>>a;
	for(int i=0;i<a.size();i++)
	{
		cnt=0;
		for(int j=i+1;j<a.size();j++)
			if(a[i]>a[j])	cnt++;
		res+=cnt*fac[a.size()-1-i];
	}
	res++;
	cout<<res<<endl;
	return 0;
}

康拓展开的逆

康拓展开的逆，就是根据康拓展开来进行逆运算，已知n的全排列，和第几大的全排列，得到具体的全排列值。

#include<bits/stdc++.h>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//提前预处理阶乘的值
vector<int> vis,res;//记录还剩下几个数可以填 ,result
int main()
{
	int n,k,t1,t2;//n的全排列,第k大的数,临时变量t 
	cin>>n>>k;
	for(int i=1;i<=n;i++)	vis.push_back(i);//填充全排列的数字 
	k--;
	for(int i=1;i<=n;i++)
	{
		t1=k/fac[n-i];
		t2=k%fac[n-i];
		if(t1!=0)	k=t2;
		res.push_back(vis[t1]);
		vis.erase(vis.begin()+t1);
	}
	for(int i=0;i<res.size();i++)
		cout<<res[i];
	cout<<endl;
	return 0;
}

下面来一道简单的例题

swust oj 437题

数字全排列
1000 （ms） 65535 （kb） 1071 / 3466
从1〜9之间顺序取Ñ个数字，组成每位数不重复的所有可能的Ñ位数，按从小到大的顺序进行编号，当输入其中的任何一个数中号是，能找出该数对应的编号。如：当N = 3，M = 132时，则输出：[123（1），132（2），213（3），231（4），312（5），321（6）] - > X = 2
输入
输入只有一行，两个正整数N和M（1≤N≤9,1≤K≤987654321），之间用一个空格分隔开。
输出
输出对应的编号X.
样例输入
3 132
样例输出
2

下面给出AC代码

#include<bits/stdc++.h>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int main()
{
	string a;
	int n,res=0,cnt;
	cin>>n>>a;
	for(int i=0;i<a.size();i++)
	{
		cnt=0;
		for(int j=i+1;j<a.size();j++)
			if(a[i]>a[j])	cnt++;
		res+=cnt*fac[a.size()-1-i];
	}
	res++;
	cout<<res<<endl;
	return 0;
}