C语言程序设计100例之（42）：康托展开
例42 康托展开
问题描述
康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成n!种不同的排列组合，康托展开表示的就是当前排列组合在n个不同元素的全排列中的名次。
例如，3个数 {1,2,3} 按从小到大的排列一共6个，分别是123、132、213、231、312、321，将这6个排列分别用自然数1、2、3、4、5、6来表示。也就是把一个自然数与一个排列对应起来。它们之间的对应关系可由康托展开来得到。
给出n（n<10）和1~n构成的一个排列，求这是第几个排列。
输入
输入包括多组测试用例。每组测试用例占两行。
第1行是一个整数n；第2行是1~n构成的一个排列。
输出
对每个测试用例。在1行中输出一个整数，表示这是第几个排列。
输入样例
1 2 3
2 1 3 4 5
5 4 3 1 2
输出样例
25
119
（1）编程思路。
例如，求321是{1，2，3}中第几个排列可以这样考虑 ：
第1位是3，当第1位的数小于3时，其排列一定位于321的前面，如123、213。小于3的数有1、2，所以有2*2!=4个；第2位是2，小于2的数只有一个就是1，所以有1*1!=1个；因此，排在321之前的{1,2,3}排列有2*2!+1*1!=5个。这样，321是第6个排列。 计算式子：2*2!+1*1!+0*0! 就是所谓的康托展开式。
再举个例子，1324是{1，2，3，4}排列中第几个排列。第1位是1，小于1的数没有，是0个， 0*3!；第2位是3，小于3的数有1和2，但1已经在第一位了，所以只有一个数2，1*2!；第3位是2，小于2的数只有1，但1已经在第1位，所以有0个数，0*1! ，所以，康托展开式为0*3!+1*2!+0*1!+0*0！=3，即1324是第3个排列。
又例如，排列357412968是{1，2，3，4，5，6，7，8，9}排列中第98884个排列。因为康托展开式为：2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884。展开式解释如下：
第1位是3，比3小的数有1和2这2个，以1、2这样的数开始的排列有8!个，即2*8!；第2位是5，比5小的数有1、2、3、4，由于3已经出现，因此有3个比5小的数，这样的数开始的排列有7!个，即3*7!；…以此类推，直至0*0!。
（2）源程序。
#include
int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
int cantor(int *a, int n) // 康托展开
{
int i,j,cnt,num=0;
for (i=0; i cnt = 0; for (j=i+1; j if (a[j] cnt++; num += fac[n-i-1]*cnt; } return num+1; } int main() { int n,a[10]; while (scanf("%d",&n)!=EOF) { int i; for (i=0;i scanf("%d",&a[i]); int ans=cantor(a,n); printf("%d\n",ans); } return 0; } 问题描述 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" 、"132"、 "213"、 "231"、 "312"、 "321"。 给定 n 和 k，返回第 k 个排列。其中，n 的范围是 [1, 9]，k 的范围是[1, n!]。 输入 输入包括多组测试用例。每组测试用例占1行，在这1行中有两个整数n和k。 输出 对每个测试用例。在1行中输出1~n构成的1个排列。 输入样例 3 3 4 9 5 16 输出样例 213 2314 14352 （1）编程思路。 先以n=5，k=16进行说明。 首先用16-1得到15 1）用15去除4! ，得到0余15；有0个数比它小的数是1，所以最高位是1； 2）用余数15去除3!，得到2余3；有2个数比它小的数是3，但1已经在之前出现过了，所以是4，即第2位为4； 3）用余数3去除2! ，得到1余1；有1个数比它小的数是2，但1已经在之前出现过了，所以是3，即第3位是3； 4）用余数1去除1! ，得到1余0。有1个数比它小的数是2，但1、3、4都出现过了，所以是5，即第4位是5； 剩下的2作为最低位。 故，k=16的排列为1 4 3 5 2。 （2）源程序。 #include int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; void uncantor(int res[],int x, int n) // 逆康托展开 { int i,j,cnt,t; int h[10]={0}; for (i = 1; i <= n; i++) { t = x / fac[n-i]; x -= t*fac[n-i]; for (j = 1, cnt=0; cnt<=t; j++) if (!h[j]) cnt++; j--; h[j] = 1; res[i-1]=j; } } int main() { int n,x,a[10]; while (scanf("%d",&n)!=EOF) { scanf("%d",&x); uncantor(a,x-1,n); int i; for (i=0;i printf("%d",a[i]); printf("\n"); } return 0; } 问题描述 现在有"abcdefghijkl”12个字符，将其所有的排列按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？ 输入 第一行有一个整数n（0 随后有n行，每行是一个排列。 输出 对于每个排列，输出一个整数m，占一行，m表示排列是第几位。 输入样例 abcdefghijkl hgebkflacdji lkjihgfedcba 输出样例 302715242 479001600 （1）编程思路。 按例42所示的康托展开式展开即可。 （2）源程序。 #include int main() { long long fact[13]; char str[15]; fact[0]=1; int i,j; for (i=1;i<=12;i++) { fact[i]=fact[i-1]*i; } int t; scanf("%d",&t); getchar(); while(t--) { gets(str); long long sum=0; int len=strlen(str); for (i=0; str[i]!='\0'; i++) { int cnt=0; for (j=i+1; str[j]!='\0'; j++) { if (str[i]>str[j]) { cnt++; } } sum+=cnt*fact[len-1-i]; } printf("%lld\n",sum+1); } return 0; } 本题选自洛谷题库 （https://www.luogu.org/problem/ P3014） 问题描述 有N（1<=N<=20）头奶牛，编号为1…N，正在与FJ玩一个疯狂的游戏。奶牛会排成一行，问FJ此时的行号是多少。之后，FJ会给奶牛们一个行号，奶牛必须按照新行号排列成线。 行号是通过以字典序对行的所有排列进行编号来分配的。比如说：FJ有5头奶牛，让它们排为行号3，排列顺序为： 1：1 2 3 4 5 2：1 2 3 5 4 3：1 2 4 3 5 因此，奶牛将排列为1、2、4、3、5。 之后，奶牛排列为“1 2 5 3 4”，并向FJ问它们的行号。继续列表： 4：1 2 4 5 3 5：1 2 5 3 4 FJ可以看到这里的答案是5。 FJ和奶牛希望你帮助玩这个游戏。 输入 第1行输入两个整数N and K 之后的2*K行描述给出的查询。每个查询占两行。 查询有两个部分：C_i将是“P”或“Q”的命令。 如果C_i是“P”，则查询的第二部分将是一个整数Ai（1 <=Ai <= N！），它是行号。此时，你需要回答正确的奶牛排列顺序。 如果C_i是“Q”，则查询的第二部分将是N个不同的整数B_j（1 <= B_j <= N）。这将表示奶牛们的一个排列，此时你需要输出正确的行号。 输出 输出k行，每行为对应查询的答案。 输入样例 5 2 1 2 5 3 4 输出样例 1 2 4 3 5 （1）编程思路。 “P”命令调用康托逆展开，“Q”命令调用康托展开。 （2）源程序。 #include long long fact[21]; long long cantor(int *a, int n) // 康托展开 { int i,j; long long cnt,num=0; for (i=0; i cnt = 0; for (j=i+1; j if (a[j] cnt++; num += fact[n-i-1]*cnt; } return num+1; } void uncantor(int res[],long long x, int n) // 逆康托展开 { int i,j; long long t,cnt; int h[21]={0}; for (i = 1; i <= n; i++) { t = x / fact[n-i]; x -= t*fact[n-i]; for (j = 1, cnt=0; cnt<=t; j++) if (!h[j]) cnt++; j--; h[j] = 1; res[i-1]=j; } } int main() { fact[0]=1; int i; for (i=1;i<=20;i++) { fact[i]=fact[i-1]*i; } int n,k,a[21]; long long x; scanf("%d%d",&n,&k); while (k--) { char op[2]; scanf("%s",op); if (op[0]=='P'){ scanf("%lld",&x); uncantor(a,x-1,n); for (i=0;i printf("%d ",a[i]); printf("\n"); } else{ for (i=0;i scanf("%d",&a[i]); x=cantor(a,n); printf("%lld\n",x); } } return 0; }习题42
42-1 逆康托展开
42-2 排第几？
42-3 奶牛排成行