推 ledia:看起來我們的作法有點像但又有點不一樣 03/18 22:14
→ suhorng:我覺得本質上是一樣的 只是我用另一種實做方法XDD 03/19 18:13
其實我覺得有個很簡單的想法~~
首先先觀察 "依照字典序" 的全排列 (暫不考慮重複的狀況)
假設要排列的字串是 abcd
1 abcd
2 abdc
3 acbd
4 acdb
5 adbc
6 adcb
7 bacd
8 badc
9 bcad
10 bcda
11 bdac
12 bdca
13 cabd
...(略)
應該能明顯注意到，對於 1~6 來講，就是把 a 當第一個字，
用剩下的 bcd 去做依字典序的全排列。而 bcd 的全排列又可以分成分別以
b, c, d 為第一個字，再接上剩下的字去做全排列產生的結果。
而對於 7~12 來講，就是把 b 當第一個字，用剩下的 acd 去做依字典序的全排列。
這應該也算一個 Divide and Conquer 的應用吧？
再來考慮有重複的情況。什麼時候我們會製造出重複的排列？
如果我們選出來的第一個字不同，那剩下的字也會不同，產生出來的全排列不會重複
所以問題就在於「選出來的第一個字相同」，此時剩下的字也會相同，
那產生出來的全排列就會重複了。
所以在遞迴時應該要避免本層選出相同的字作首。
怎麼實做見仁見智，我習慣一開始先把字串 sort 一次~
以下這份程式不考慮設計結構的問題噢:)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
char str[80], out[80];
void dfs(int x) {
if (str[x] == 0) {
out[x] = 0;
printf("%s\n", out);
return;
}
out[x] = -1;
for (int i=0; str[i]; i++) {
if (str[i]!=-1 && str[i]!=out[x]) {
out[x] = str[i];
str[i] = -1;
dfs(x+1);
str[i] = out[x];
}
}
}
int main() {
scanf("%s", str);
std::sort(str, str+strlen(str));
dfs(0);
system("PAUSE");
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.152.140
※ 編輯: suhorng 來自: 218.160.152.140 (03/18 21:22)
※ 編輯: suhorng 來自: 218.160.152.140 (03/18 21:22)