例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行中輸出一個整數，表示這是第幾個排列，
輸入樣例
3
1 2 3
5
2 1 3 4 5
5
5 4 3 1 2
輸出樣例
1
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 <stdio.h>
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<n; i++) {
cnt = 0;
for (j=i+1; j<n; j++)
if (a[j]<a[i])
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<n;i++)
scanf("%d",&a[i]);
int ans=cantor(a,n);
printf("%d\n",ans);
}
return 0;
}
習題42
42-1 逆康托展開
問題描述
給出集合 [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 <stdio.h>
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<n;i++)
printf("%d",a[i]);
printf("\n");
}
return 0;
}
42-2 排第幾？
問題描述
現在有"abcdefghijkl”12個字符，將其所有的排列按字典序排列，給出任意一種排列，說出這個排列在所有的排列中是第幾小的？
輸入
第一行有一個整數n（0<n<=10000）；
隨后有n行，每行是一個排列，
輸出
對于每個排列，輸出一個整數m，占一行，m表示排列是第幾位，
輸入樣例
3
abcdefghijkl
hgebkflacdji
lkjihgfedcba
輸出樣例
1
302715242
479001600
（1）編程思路，
按例42所示的康托展開式展開即可，
（2）源程式，
#include <stdio.h>
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;
}
42-3 奶牛排成行
本題選自洛谷題庫 （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
P
3
Q
1 2 5 3 4
輸出樣例
1 2 4 3 5
5
（1）編程思路，
“P”命令呼叫康托逆展開，“Q”命令呼叫康托展開，
（2）源程式，
#include <stdio.h>
long long fact[21];
long long cantor(int *a, int n) // 康托展開
{
int i,j;
long long cnt,num=0;
for (i=0; i<n; i++) {
cnt = 0;
for (j=i+1; j<n; j++)
if (a[j]<a[i])
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<n;i++)
printf("%d ",a[i]);
printf("\n");
}
else{
for (i=0;i<n;i++)
scanf("%d",&a[i]);
x=cantor(a,n);
printf("%lld\n",x);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/401404.html
標籤：其他