康拓展开及其逆运算和全排列函数
有所摘抄，但重要的是自己的想法。
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
X = a[n]*(n-1)! + a[n-1]*(n-2)! + ... + a[i]*(i-1)! + ... + a[1]*0!
index: 1 2 ... n-i+1 ... n
其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n
a[i] 是：假设 一串数字中第index个元素为e， a[i]表示第index个数e之后的数比e小的数的个数
举个例子：
原序列： 1 2 3 4 5 6 7 8
求： 3 5 7 4 1 2 9 6 8
X = 2*8! + 3*7! + 4*6! + 2*5! + 0*4! + 0*3! + 2*2! + 0*1! + 0*0! = 98884.
解释：
排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!
排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!
以此类推，直至0*0!
用途：
显然，n位（0~n-1）全排列后，其康托展开唯一且最大约为n!，因此可以由更小的空间来储存这些排列。由公式可将X逆推出对应的全排列。
总之就是用来压缩空间的。。本人也不大懂。
例题：
现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？
每行输入一行字符串，保证是a~l这12个字符的某种排列
EOF结束
输出一个整数，代表这个排列排在第几位
abcdefghijkl
abcdefghiklj
gfkedhjblcia
1
4
260726926
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
int factorial(int l){
if(l == 0 || l == 1) return 1;
else return l * factorial(l-1);
}
int main(){
char a[13];
LL ans;
int i, j, k;
while(~scanf("%s", a+1)){
ans = 1;
for(i = 1; i <= 12; ++i){
k = 0;
for(j = i+1; j <= 12; ++j)
if(a[j] < a[i]) ++k;
ans += factorial(12-i) * k;
}
printf("%lld\n", ans);
}
return 0;
}
另外，康托展开的逆运算，即通过知道它是第几个全排列求全排列
例1 {1,2,3,4,5}的全排列，并且已经从小到大排序完毕
(1)找出第96个数
首先用96-1得到95
用95去除4! 得到3余23
有3个数比它小的数是4
所以第一位是4
用23去除3! 得到3余5
有3个数比它小的数是4但4已经在之前出现过了所以第二位是5（4在之前出现过，所以实际比5小的数是3个）
用5去除2!得到2余1
有2个数比它小的数是3，第三位是3
用1去除1!得到1余0
有1个数比它小的数是2，第二位是2
最后一个数只能是1
所以这个数是45321
(2)找出第16个数
首先用16-1得到15
用15去除4!得到0余15
用15去除3!得到2余3
用3去除2!得到1余1
用1去除1!得到1余0
有0个数比它小的数是1
有2个数比它小的数是3 但由于1已经在之前出现过了所以是4（因为1在之前出现过了所以实际比4小的数是2）
有1个数比它小的数是2 但由于1已经在之前出现过了所以是3（因为1在之前出现过了所以实际比3小的数是1）
有1个数比它小得数是2 但由于1，3，4已经在之前出现过了所以是5（因为1，3，4在之前出现过了所以实际比5小的数是1）
最后一个数只能是2
所以这个数是14352
最后，还有一个全排列函数 ：next_permutation函数
这是一个求一个排序的下一个排列的函数，可以遍历全排列,要包含头文件<algorithm>
与之完全相反的函数还有prev_permutation
与之完全相反的函数还有prev_permutation
但做本题是会超时（不用想也是，一个一个求肯定TLE）
该函数可以对很多类型的数组序列进行求下一个字典序排列，即按全排的顺序求下一个排序序列
这里也贴一下本题的TLE代码（嘿嘿）
//TLE
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
char b[20];
int res;
while(~scanf("%s", b)){
char a[] = "abcdefghijkl";
char aa[] = "gfkedhjblcia"
if(strcmp(a, b) == 0) {printf("1\n"); continue;}
res = 1;
while(next_permutation(a, a+12)){
++res;
if(strcmp(a, b) == 0) {
printf("%d\n", res);
break;
}
}
}
return 0;
}此函数各种类型的用法详解：http://blog.sina.com.cn/s/blog_9f7ea4390101101u.html
2017/4/1日增：
1.
//康拓代码实现
#include <bits/stdc++.h>
using namespace std;
int factor(int k){
if(k == 0 || k == 1) return 1;
return k * factor(k-1);
}
int main(){
int n, i, ans, k;
char jk[25];
while(cin >> jk+1){
ans = 0, n = strlen(jk+1);
for(i = 1; i <= n; ++i){
k = 0;
for(int j = i+1; j <= n; ++j)
if(jk[i] > jk[j]) ++k;
ans += k * factor(n-i);
}
cout << ans+1 << endl; //最小序列ans为0，同理ans+1；
}
return 0;
}//逆康拓代码实现
#include <bits/stdc++.h>
using namespace std;
int factor(int k){
if(k == 0 || k == 1) return 1;
return k * factor(k-1);
}
int ans[105], book[105];
int main(){
int n, k, m, key, x, j;
while(cin >> n >> m){
memset(book, 0, sizeof book);
--n; //最小序列ans为0，所以需要--；
for(int i = 1; i <= m; ++i){
k = factor(m-i);
key = n/k+1; //在(m-i)!的系数+1，即当前位置的数值大于后面的个数+1，+1为了方便后面求该数
n %= k; //更新n
j = 1; //初始化j
while(key){
if(!book[j]) --key;
++j;
}
ans[i] = j-1; //当找到该数时j多加了一次1
book[j-1] = 1;
}
for(int i = 1; i <= m; ++i)
printf("%d", ans[i]);
printf("\n");
}
return 0;
}