花式全排列，不服不行（康拓展开）

偶尔做了些蓝桥杯练习题，发现一题全排列，看着简单以为C++全排列库直接暴力就行，然而……答案数据高达229526多亿

基础秀

#include <iostream>
#include <algorithm>   
using namespace std;
int main () {
    char dp[] = "abcd";
    do{
        cout<<dp[0]<<" "<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<endl; 
    }while( next_permutation(dp,dp+4) );  
    return 0;
}

我们来看看这短短10行代码的输出结果

a b c d
a b d c
a c b d
a c d b
a d b c
a d c b
b a c d
b a d c
b c a d
b c d a
b d a c
b d c a
c a b d
c a d b
c b a d
c b d a
c d a b
c d b a
d a b c
d a c b
d b a c
d b c a
d c a b
d c b a

是不是感觉很棒？短短10行代码就实现了全排列……那我要输出……比如abcd开始的第8个是什么，要怎么实现？

#include <iostream>
#include <algorithm>   
using namespace std;
int main () {
    char dp[] = "abcd";
    int temp = 0;
    do{
        temp++;
        if(temp == 8) cout<<dp[0]<<" "<<dp[1]<<" "<<dp[2]<<" "<<dp[3]<<endl;
    }while( next_permutation(dp,dp+4) );  
    return 0;
}

的确，加一个计数器不就好了，哪里难了。那……请问如果是从abcdefghijklmnopq开始，然后要求第22952601027516全排列数是什么？你怎么求？？？的确，搏心态试一试，我试了10亿，也就是1000000000，用了27秒。估算了一下，22952601027516大概需要7天才能算出来……

花式秀

首先把那题练习题拿出来。

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

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

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

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

也就是，给你第n个数的全排列方式，让你求这个数n是多少。废话不多说，直接上代码。

#include <iostream>
#include <string>
using namespace std;  
int main() {  
    int flag[113] = {0};
    string ss="bckfqlajhemgiodnp";  
    long long int sum=0;  
    long long int ans[18]; 
    ans[0]=1;  
    for(int i=1;i<=16;i++) 
        ans[i]=ans[i-1]*i;  
    for(int i=0;i<=16;i++) {  
        for(int j='a';j<ss[i];j++)
            if(flag[j]==0)   
                sum+=ans[16-i];
        flag[ss[i]] = 1; 
    }  
    cout<<sum<<endl;  
    return 0;  
}  

写了这么久之后忽然回过来发现，这个算法是，康拓展开，而下面的，则是康拓展开的逆运算。原理就是通过将一个全排列压缩这个一个X进行存储，从而达到压缩空间的效果

解析一波

• 这段代码的主要思想其实就是模拟。首先用ans来标记该字符串的第n个位置的权值。即第n位如果要变动，每变动一个都需要将位数增加(n-1)!。

• 例如：abcd->dcba，第3位(从右往左)本来是a，然后变成了d，途经了a->b->c->d。所以，sum += 3×3! 。第2位本来是a，然后变成了c。途经了a->b->c，所以，sum += 2×2!。第1位本来是a，然后变成了b，需要途经a->b，所以sum += 1!。第0位是 a不变，所以结果是6×3+2×2+1 = 23

• 这里需要注意的是，如果abcd->bdca，第3位是sum += 1×3!，但是第2位，a->d中途经的是a->c->d，因为b在之前已经被使用过了，所以不被途经。

OK，那判断这个字符串是第几个全排列的我知道了，如果我已知的是n，需要得到的是全排列的字符串呢？

#include <iostream>
#include <string>
using namespace std;  
int main() {  
    long long int ans[18];
    long long int num;
    ans[0]=1;  
    for(int i=1;i<=18;i++) 
        ans[i]=ans[i-1]*i; 
    while(cin>>num){
        string ss="abcdefghijklmnopq";
        int flag[200] = {0};
        int len = ss.size();  
        for(int i=len; i>=1; i--){
            char ch = 'a';
            while(flag[ch]==1) ch += 1;
            while(num>=ans[i-1]){
                ch += 1;
                while(flag[ch]==1) ch += 1;
                num -= ans[i-1];
            }
            ss[len-i] = ch;
            flag[ch] = 1;
        }
        cout<<ss<<endl;
    }
    return 0;  
}  

把代码稍微改编下就能达到要求了，但是需要注意long long int的最大值是9223372036854775807。

最后留下一个小常识，在全局变量中定义的int数组的默认值都是0，而在主函数中定义的int数组的值是随机的。试试如下代码

#include <iostream>
using namespace std;
int a[10];    //作为全局变量
int main(int argc, char *argv[]){
    //int a[10];    在主函数中定义
    for(int i=0; i<10; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}