康托展开
发布时间：2020-12-13 20:42:38 所属栏目：PHP教程 来源：网络整理
导读：康托展开是组合数学的经典问题 康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。 那末，对n个数的排列，康托展开为： 其中表示第i个元素在未出现的元素中排列第几。举个简单的例子： 对排列4213来讲，4在4213中排
|
康托展开是组合数学的经典问题 康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。 //康托展开
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;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |