- 注：代码很长，不要害怕，不难的，核心代码只有几行，贴上完整代码是为了大家测试方便。
-
首先明确我们要求的是什么样的题目。
-
例如，给定数组a[10] = {1,2,3,4,5,6,7,8,9,10};
-
我们把排列{1,2,3,4,5,6,7,8,9,10}规定为0
-
我们把排列{1,2,3,4,5,6,7,8,10,9}规定为1
-
......
-
现给定排列{2,3,5,1,4,6,8,7,9,10} 代表的是多少?
-
当然，我们可以通过递归求解a数组的全排列，并且计数并判断当前全排列是否是要求的全排列，如果是，那么输出结果。
-
我们知道当有n个数的时候他的全排列数字是n！个，当n较大时，通过递归(或者使用全排列函数)去枚举，时间效率是非常低的。那么怎么办呢？
-
有一个神奇的公式叫做康托展开式：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，
-
其中a[i]为当前未出现的元素中是排在第几个（从0开始）。
-
那么我们通过模拟就可以很快的写出代码：
-
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 1000
using namespace std;
/*
全排列散列 康托展开
*/
// 求阶乘
LL fac(int x){LL ans = 1;for(int i = 2; i <= x; i++){ans *= i; }return ans;
}
LL ans;
int n;
int a[100];
void arrayToInt(){for(int i = 0; i < n; i++){int temp = 0;for(int j = i+1; j < n; j++){if(a[j] < a[i]) temp++; }ans += temp * fac(n-i-1); }printf("%lld\n",ans);
}
int main(){
// freopen("input.txt","r",stdin);scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%d",&a[i]);}arrayToInt();return 0;
}-
-
既然我们可以通过全排列求出这个全排列是第几个，
-
那么，如果我们知道某个全排列是第几个，是否也可以求出这个全排列是什么样的呢？
-
那我们将上面的公式倒推一下就可以。
-
叫做逆康托展开式(也有的称为康托逆展开式)。
-
即我们知道了X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!其中X 知道 求解a[ 1 ] - a[ n ]
-
注：X是从0开始
-
这里我们举个例子来说明：
-
已知序列1 2 3 4求编号为 3 的序列是什么(1 3 4 2)
-
3 / 3! = 0 余 3
-
3 / 2! = 0 余 3
-
3 / 1! = 3 余 0
-
0 / 0! (这里不操作)
-
(上一个算式的余数是下一个算式的被除数，每个算式的商是对应的a数组中算数)
-
由上可知，
-
比第一个数小的数有0个,
-
比第二个数小的有0个，
-
比第三个数小的有3个
-
即a[ 4 ] = 0, 所以第一个数是1
-
a[ 3 ] = 0, 因此1已经用过，所以第二个数是2a[ 2 ] = 3,
-
所以第三个数是4a[ 3 ] 最后剩下2 ，
-
所以第四个数字是2
-
同样的，我们只需要模拟算法的过程即可得到代码：
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 1000
using namespace std;
/*
全排列散列 康托展开
*/
// 求阶乘
LL fac(int x){LL ans = 1;for(int i = 2; i <= x; i++){ans *= i; }return ans;
}
LL ans;
int n;
int a[100];
int used[100];
void intToArray(int x){memset(used, 0, sizeof(used));int i, j, temp;for(i = 0; i < n; i++){temp = x / fac(n-i-1); for(j = 1; j <= n; j++){if(!used[j]){if(temp == 0) break;temp --; }}a[i] = j; used[j] = 1;x %= fac(n-i-1);}for(int i = 0; i < n; i++){printf("%d ",a[i]); }
}
int main(){freopen("input.txt","r",stdin);scanf("%d",&n);for(int i = 0; i < 10; i++){intToArray(i); puts("");}return 0;
}-
-
康托展开是个特殊的哈希函数，当然他还有别的应用，，比如在搜索问题中，我们可以对vis数组进行压缩，如八数码问题。