偶爾做了些藍(lán)橋杯練習(xí)題，發(fā)現(xiàn)一題全排列锉罐，看著簡單以為C++全排列庫直接暴力就行，然而……答案數(shù)據(jù)高達229526多億
基礎(chǔ)秀
#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行代碼的輸出結(jié)果
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行代碼就實現(xiàn)了全排列……那我要輸出……比如abcd開始的第8個是什么脓规，要怎么實現(xiàn)？
#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;
}
的確业舍，加一個計數(shù)器不就好了抖拦，哪里難了。那……請問如果是從abcdefghijklmnopq開始舷暮，然后要求第22952601027516全排列數(shù)是什么态罪？你怎么求？下面？复颈？的確，搏心態(tài)試一試沥割，我試了10億耗啦，也就是1000000000，用了27秒机杜。估算了一下帜讲，22952601027516大概需要7天才能算出來……
花式秀
首先把那題練習(xí)題拿出來。
X星系的某次考古活動發(fā)現(xiàn)了史前智能痕跡椒拗。
這是一些用來計數(shù)的符號似将，經(jīng)過分析它的計數(shù)規(guī)律如下：
（為了表示方便获黔，我們把這些奇怪的符號用a~q代替）
abcdefghijklmnopq 表示0
abcdefghijklmnoqp 表示1
abcdefghijklmnpoq 表示2
abcdefghijklmnpqo 表示3
abcdefghijklmnqop 表示4
abcdefghijklmnqpo 表示5
abcdefghijklmonpq 表示6
abcdefghijklmonqp 表示7
.....
在一處石頭上刻的符號是：
bckfqlajhemgiodnp
請你計算出它表示的數(shù)字是多少？
也就是在验，給你第n個數(shù)的全排列方式玷氏，讓你求這個數(shù)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;
}
寫了這么久之后忽然回過來發(fā)現(xiàn)，這個算法是块饺，康拓展開赞辩，而下面的，則是康拓展開的逆運算刨沦。原理就是通過將一個全排列壓縮這個一個X進行存儲诗宣，從而達到壓縮空間的效果
解析一波
這段代碼的主要思想其實就是模擬。首先用ans來標(biāo)記該字符串的第
n個位置的權(quán)值想诅。即第n位如果要變動召庞，每變動一個都需要將位數(shù)增加(n-1)!。例如：
abcd->dcba来破，第3位(從右往左)本來是a篮灼，然后變成了d，途經(jīng)了a->b->c->d徘禁。所以诅诱，sum += 3×3!。第2位本來是a送朱，然后變成了c娘荡。途經(jīng)了a->b->c，所以驶沼，sum += 2×2!炮沐。第1位本來是a，然后變成了b回怜，需要途經(jīng)a->b大年，所以sum += 1!。第0位是a不變玉雾，所以結(jié)果是6×3+2×2+1 = 23這里需要注意的是翔试，如果
abcd->bdca，第3位是sum += 1×3!复旬，但是第2位垦缅，a->d中途經(jīng)的是a->c->d，因為b在之前已經(jīng)被使用過了驹碍，所以不被途經(jīng)壁涎。
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
這題也是類似的使用康拓展開的思想，把數(shù)組每個下標(biāo)對應(yīng)的位置賦予不同的權(quán)值延刘，這題不同的在于漫试，權(quán)值由每個每個n對應(yīng)的分組表示，具體代碼與注釋如下：
#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++) //標(biāo)記每個分組的權(quán)值
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]; //取得對應(yīng)的分組編號碘赖，t+1為分組編號
tmp = t+1; //緩存數(shù)據(jù)驾荣，用來找第一個沒使用過得第tmp大小的數(shù)
for (int i=1; i<=20; i++) { //找符合條件的數(shù)
if (tmp==1 && flag[i]==0) {
cot = i;
break;
} else if (flag[i]==0) tmp--;
}
flag[cot] = 1; //標(biāo)記已經(jīng)使用過
cout<<cot; //輸出數(shù)據(jù)
m = m - ans[n]*t - 1; //新的m值需要減去前面的所有組數(shù)和本組的一個空組
n--;
if (n&&m) cout<<" "; //空格要求
}
cout<<endl;
}
return 0;
}
最后留下一個小常識，在全局變量中定義的int數(shù)組的默認(rèn)值都是0普泡，而在主函數(shù)中定義的int數(shù)組的值是隨機的播掷。試試如下代碼
#include <iostream>
using namespace std;
int a[10]; //作為全局變量
int main(int argc, char *argv[]){
//int a[10]; 在主函數(shù)中定義
for(int i=0; i<10; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
