全排列的编码与解码——【康托展开及其逆运算】

参考过程：点击打开链接

参考代码：点击打开链接

康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。

 

那么，对于n个数的排列，康托展开为：

 

其中表示第i个元素在未出现的元素中排列第几。举个简单的例子：

 

对于排列4213来说，4在4213中排第3，注意从0开始，2在213中排第1，1在13中排第0，3在3中排第0，即：

 

，这样得到4213在所有排列中排第ans=20

 

代码实现：(从0开始计数)

 

[cpp]  view plain  copy   //康托展开   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-1];  //f[]为阶乘       }       return ans;  //返回该字符串是全排列中第几大，从1开始   }  

 

康托展开的逆运算：就是根据某个排列的在总的排列中的名次来确定这个排列。比如：

 

求1234所有排列中排第20的是啥，那么就利用辗转相除法确定康托展开中的系数，然后每次输出当前未出现过的第个元素。

 

代码实现康托展开逆运算：

 

[cpp]  view plain  copy   //康托展开逆运算   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-1];           LL t = n / f[i-1];           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;   }  

Problem C: 排列序数(21分)

Description

X星系的某次考古活动发现了史前智能痕迹。 这是一些用来计数的符号，经过分析它的计数规律如下： （为了表示方便，我们把这些奇怪的符号用a~q代替）

abcdefghijklmnopq 表示0 abcdefghijklmnoqp 表示1 abcdefghijklmnpoq 表示2 abcdefghijklmnpqo 表示3 abcdefghijklmnqop 表示4 abcdefghijklmnqpo 表示5 abcdefghijklmonpq 表示6 abcdefghijklmonqp 表示7 .....

在一处石头上刻的符号是： bckfqlajhemgiodnp

请你计算出它表示的数字是多少？

请输出该整数，不要输出任何多余的内容，比如说明或注释。

（注：蓝桥杯比赛时，此题为填空题，直接填写答案即可）

Input

无

Output

无

Sample Input

无

Sample Output

无 #include<stdio.h> #include<math.h> #include<stdlib.h> #include<string.h> long long fun(long long n){ long long s = 1; for(int i = 1;i<=n;i++) s*=i; return s; } int main(){ int f[18] = {0}; int dig[] = {0,2,3,11,6,17,12,1,10,8,5,13,7,9,15,4,14,16}; long long sum = 0; for(int i = 1;i<18;i++){ long long t = 0; for(int j = 1;j<18;j++){ if(j==dig[i]){f[j]=1;break;} if(f[j]==0)t++; } sum+=(t)*fun(18-1-i);//此处康托展开式公式 } printf("%lld",sum); return 0; } 或 [cpp]  view plain  copy  print ? #include <cstdio>   #include <cstring>   #include <iostream>   #include <algorithm>   using namespace std;   #define ll long long      ll pow(ll a)   {       ll s = 1;       for(ll i = 1; i <= a; i++)           s *= i;       return s;   }      int main()   {       char s[18]="bckfqlajhemgiodnp";//17长度       ll a, ans = 0, k;       for(int i = 0; i < 16; i++)       {           k = 0;           for(int j = i+1; j < 17; j++)               if(s[i] > s[j]) k++;           ans += k * pow(16-i);       }       printf("%lld\n", ans);       return 0;   }      /**  根据题意，可知题目计算的为全排列的次数  然后找规律  0123 0   0*3! + 0*2! + 0*1! = 0  0132 1   0*3! + 0*2! + 1*1! = 1  0213 2   0*3! + 1*2! + 0*1! = 2  0231 3   0*3! + 1*2! + 1*1! = 3  0312 4   0*3! + 2*2! + 0*1! = 4  0321 5   0*3! + 2*2! + 1*1! = 5  1023 6   1*3! + 0*2! + 0*1! = 6  1032 7   1*3! + 0*2! + 1*1! = 7  1203 8   1*3! + 1*2! + 0*1! = 8  1230 9   1*3! + 1*2! + 1*1! = 9  1302 10  1*3! + 2*2! + 0*1! = 10  1320 11  1*3! + 2*2! + 1*1! = 11  2013 12  2*3! + 0*2! + 0*1! = 12  2031 13  2*3! + 0*2! + 1*1! = 13  2103 14  2*3! + 1*2! + 0*1! = 14  2130 15  2*3! + 1*2! + 1*1! = 15  2301 16  2*3! + 2*2! + 0*1! = 16  2310 17  2*3! + 2*2! + 1*1! = 17  3012 18  3*3! + 0*2! + 0*1! = 18  3021 19  3*3! + 0*2! + 1*1! = 19  3102 20  3*3! + 1*2! + 0*1! = 20  3120 21  3*3! + 1*2! + 1*1! = 21  3201 22  3*3! + 2*2! + 0*1! = 22  3210 23  3*3! + 2*2! + 1*1! = 23    可以得出规律，比后面大的个数 * (i-1)!  查询资料可知，此为[康托展开式] 答案：22952601027516  */