偶尔做了些蓝桥杯练习题，发现一题全排列，看着简单以为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。
相似题目扩展
在题库中，不止有这些康拓展开的裸题，还有一些类似康拓展开的题目。比如HDU2062
这题也是类似的使用康拓展开的思想，把数组每个下标对应的位置赋予不同的权值，这题不同的在于，权值由每个每个n对应的分组表示，具体代码与注释如下：
#include <iostream>
#include <string.h>
using namespace std;
long long int ans[22],m;
int main(int argc, const char * argv[]) {
int n,t,tmp,cot = 0,flag[22];
ans[0] = 0;
for (int i=1; i<21; i++) //标记每个分组的权值
ans[i] = (i-1)*ans[i-1] + 1;
while (cin>>n>>m) { //注意m是long long int型的
memset(flag, 0, sizeof(flag));
while (m&&n) {
t = (m-1)/ans[n]; //取得对应的分组编号，t+1为分组编号
tmp = t+1; //缓存数据，用来找第一个没使用过得第tmp大小的数
for (int i=1; i<=20; i++) { //找符合条件的数
if (tmp==1 && flag[i]==0) {
cot = i;
break;
} else if (flag[i]==0) tmp--;
}
flag[cot] = 1; //标记已经使用过
cout<<cot; //输出数据
m = m - ans[n]*t - 1; //新的m值需要减去前面的所有组数和本组的一个空组
n--;
if (n&&m) cout<<" "; //空格要求
}
cout<<endl;
}
return 0;
}
最后留下一个小常识，在全局变量中定义的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;
}
