康托展開
來源：程序員人生 發布時間：2015-06-05 08:59:17 閱讀次數：3512次
康托展開是組合數學的經典問題
康托展開表示的是當前排列在n個不同元素的全排列中的名次。比如213在這3個數所有排列中排第3。
那末，對n個數的排列，康托展開為：
其中表示第i個元素在未出現的元素中排列第幾。舉個簡單的例子：
對排列4213來講，4在4213中排第3，注意從0開始，2在213中排第1，1在13中排第0，3在3中排第0，即：
，這樣得到4213在所有排列中排第ans=20
代碼實現：(從0開始計數)
//康托展開
LL Work(char str[])
{
int len = strlen(str);
LL ans = 0;
for(int i=0; i<len; i++)
{
int tmp = 0;
for(int j=i+1; j<len; j++)
if(str[j] < str[i]) tmp++;
ans += tmp * f[len-i⑴]; //f[]為階乘
}
return ans; //返回該字符串是全排列中第幾大，從1開始
}
康托展開的逆運算：就是根據某個排列的在總的排列中的名次來肯定這個排列。比如：
求1234所有排列中排第20的是啥，那末就利用展轉相除法肯定康托展開中的系數，然后每次輸出當前未出現過的第個元素。
代碼實現康托展開逆運算：
//康托展開逆運算
void Work(LL n,LL m)
{
n--;
vector<int> v;
vector<int> a;
for(int i=1;i<=m;i++)
v.push_back(i);
for(int i=m;i>=1;i--)
{
LL r = n % f[i⑴];
LL t = n / f[i⑴];
n = r;
sort(v.begin(),v.end());
a.push_back(v[t]);
v.erase(v.begin()+t);
}
vector<int>::iterator it;
for(it = a.begin();it != a.end();it++)
cout<<*it;
cout<<endl;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
