大貓咪的新玩具找出所有排列的結果，利用 C++ 快速解決排列問題！
排列組合是學生時期的夢魘，各式各樣的題目要我們計算。
如今總算可以用電腦來計算了，也可以直接列舉所有的排列。
接下來就來看看如何寫出有效率的程式吧 ~~
排列組合共有兩大部分：排列和組合 (廢話)
今天我們先講牌列的部分。
排列
假如目前我們有 3 個杯子，分別稱做 ABC。
那一共有 6 種可能 ($3! = 6$)。
分別為：
- ABC
- ACB
- BAC
- BCA
- CBA
- CAB
那我們要怎麼列舉出這 6 種狀況？
如果是平常，我們都怎麼做？
如果是我，我都是先選擇第一個位子的杯子要放什麼
接著我們再選擇第二個位子的杯子要放什麼
~~接著我們再選擇第三個位子的杯子要放什麼 ~~
其實不用選，選了兩個之後，就只剩下一個選擇了
…
那在程式上來說也是這樣，每個位子我們都選擇一個杯子來放。
所以程式寫起來也是這樣：
std::vector<char> arr = {'A', 'B', 'C'};
// 選擇第一個位子
for(int i = 0; i < 3; ++i){
// 把選擇到的往前放，後面的就都是還沒被挑過的
std::swap(arr[0], arr[i]);
// 選擇第二個位子
for(int j = 1; j < 3; ++j){
std::swap(arr[1], arr[j]);
// 輸出
for(int k = 0; k < 3; ++k){
std::cout << arr[k];
}
std::cout << std::endl;
std::swap(arr[1], arr[j]);
}
// 記得換回來
std::swap(arr[0], arr[i]);
}那因為排列的數量不可能都是只有 3 個，因此我們可以改用遞迴寫。
void perm(std::vector<char> &arr, int idx){
if(idx == arr.size()-1){ // 都選擇完了
for(int i = 0; i < arr.size(); ++i){
std::cout << arr[i];
}
std::cout << "\n";
}else{
for(int i = idx; i < arr.size(); ++i){
std::swap(arr[idx], arr[i]);
perm(arr, idx+1);
std::swap(arr[idx], arr[i]);
}
}
}
std::vector<char> arr = {'A', 'B', 'C'};
perm(arr, 0);重複牌列
上方的舉例是沒有重複的情況，那如果有重複呢？
如果有重複的話，用上面的方法會產生出重複的排列
那如果我們要產生不重複的排列怎麼辦？
其實只要稍微修改就好了
在選擇每個位子的杯子的時候，我們只要挑選不重複的杯子
這樣產生出的結果就不會重複了
於是大概就像是這樣：
void perm(std::vector<char> &arr, int idx){
if(idx == arr.size()-1){ // 都選擇完了
// 輸出
for(int i = 0; i < arr.size(); ++i){
std::cout << arr[i];
}
std::cout << "\n";
}else{
for(int i = idx; i < arr.size(); ++i){
bool duplicate = false;
for(int j = idx; j < i; ++j){
if(arr[j] == arr[i]){
duplicate = true;
break;
}
}
if(duplicate) continue;
std::swap(arr[idx], arr[i]);
perm(arr, idx+1);
std::swap(arr[idx], arr[i]);
}
}
}
std::vector<char> arr = {'A', 'A', 'C'};
std::sort(arr.begin(), arr.end()); // 先都依照大小排列過
perm(arr, 0);Lexicographic permutation
另一個方法就是用字典序的方式來產生
首先要把陣列由小到大排列好，然後此陣列就作為第一個排列
接著要產生下一個排列，以下步驟：
由右至左找尋第一組非升序(非嚴格升序)的相鄰元素，如未找到，則沒有下一組排列，排列到此結束
將非升序的相鄰元素稱作 a 和 b (a < b)，則在 a 的右邊 (包含 b) 找到大於 a 且最靠近右者，稱作 c
將 a 和 c 交換
從原始 a 的位置開始向右的元素們前後顛倒
舉例：
假設陣列元素為 ABAC，則由小至大排序後為 AABC，此為第一個排列
起始為 AABC，我們發現由右往左找，則 BC 這組相鄰元素是第一組不是升序的
則我們在 B 的右邊找最靠近右者且大於 B 的元素，因為 B 的右邊只有 C，因此答案就是 C
我們將 B 和 C 交換，則變為 AACB
因為 B 的原始位置為 2 (從 0 開始)，則我們將 3 開始的元素都顛倒，但由於只有一個元素，因此顛倒後依然相同為 AACB
(接著下一個排列為 ABAC)
bool lexicographic(std::vector<char> &arr){
// 步驟 1
int idx;
for(idx = arr.size()-2; idx >= 0; idx--){
if(arr[idx] < arr[idx+1]) break;
}
if(idx == -1) return false;
// 步驟 2
auto it = std::upper_bound(arr.rbegin(), arr.rend()-idx-1, arr[idx]);
int swap_idx = arr.size() - (it - arr.rbegin() + 1);
// 步驟 3
std::swap(arr[idx], arr[swap_idx]);
// 步驟 4
std::reverse(arr.begin()+idx+1, arr.end());
return true;
}
std::vector<char> arr = {'A', 'B', 'A', 'C'};
std::sort(arr.begin(), arr.end()); // 先都依照大小排列過
// 找出所有排列
do{
for(char c : arr){
std::cout << c;
}
std::cout << std::endl;
}while(lexicographic(arr));std::next_permutation
如果你說：我不想自己寫，有沒有內建的？
有，C++ 內建有 next_permutation，可以簡單就達到字典排序的效果
不過一樣要先記得依照大小排好
std::vector<char> arr = {'A', 'A', 'C'};
std::sort(arr.begin(), arr.end()); // 先都依照大小排列過
do{
// 輸出
for(int i = 0; i < arr.size(); ++i){
std::cout << arr[i];
}
std::cout << "\n";
}while(std::next_permutation(arr.begin(), arr.end()));Reference
如果你覺得這篇文章有用 可以考慮贊助飲料給大貓咪