C++ prev_permutation 函數詳解與全排列遍歷技巧

C++ prev_permutation 函數詳解

`prev_permutation` 是 `` 中的函數，將序列重排為字典序前一個排列。返回 `true` 若存在前一個排列，`false` 若已是第一個（升序）排列，並將序列重置為最後一個（降序）。

基本用法

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    int a[] = {3, 2, 1}; // 從最後一個排列開始
    do {
        for(int x : a) cout << x << ' ';
        cout << '\n';
    } while(prev_permutation(a, a+3));
    // 輸出: 3 2 1, 3 1 2, 2 3 1, 2 1 3, 1 3 2, 1 2 3
}

與 next_permutation 對比

• `next_permutation`：生成下一個（字典序更大）排列，從升序開始遍歷所有排列。
• `prev_permutation`：生成上一個（字典序更小）排列，從降序開始遍歷所有排列。

常見模式

1. 數組全排列遍歷

sort(a, a+n); // 必須從升序開始
do {
    // 處理當前排列 a
} while(next_permutation(a, a+n));

2. 字符串全排列

string s = "abc";
sort(s.begin(), s.end());
do {
    cout << s << '\n';
} while(next_permutation(s.begin(), s.end()));

3. 指定長度排列

// 僅對前 k 個元素排列
while(next_permutation(a, a+k)) { ... }

4. 自定義比較函數

bool cmp(char a, char b) {
    if(tolower(a) != tolower(b)) return tolower(a) < tolower(b);
    return a < b; // 大寫在小寫前
}
sort(ch, ch+len, cmp);
do {
    puts(ch);
} while(next_permutation(ch, ch+len, cmp));

進階技巧

• 跳過重複排列：輸入含重複元素時，`next_permutation` 會生成重複排列。需先排序，配合 `unique` 或手動去重。
• 部分排列：只對前 k 個元素排列，其餘固定。
• 逆序遍歷：從降序開始用 `prev_permutation` 遍歷所有排列。

注意事項

1. 範圍必須有效：`first < last`，且迭代器可解引用、可增減。
2. 若序列已是最小排列（升序），調用 `prev_permutation` 會變為最大排列（降序）並返回 `false`。
3. 對於 `string`、`vector` 等容器，用 `begin()`、`end()`。

總結

`prev_permutation`/`next_permutation` 是 C++ 標準庫中高效生成排列的工具，配合排序可遍歷全排列，支持自定義比較，是組合生成問題的利器。