next_permutation 是 STL 中生成下一字典序排列的核心算法，廣泛用於全排列枚舉、組合優化問題。本文深度剖析其遞增原理、實現步驟、使用陷阱與 prev_permutation 對比。
1. 函數原型
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
template <class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comp);
- 要求：雙向迭代器（
vector、list、deque、數組）
- 默認比較：
operator<（字典序升序）
- 返回：
true 生成下一排列；false 已是最大排列，重置為最小排列
2. 遞增原理：字典序最小增量
對序列 a[0]...a[n-1]，目標找到比當前大的最小排列：
- 從右向左找第一個
a[i] < a[i+1] 的位置 i（稱作「支點」）
- 若不存在（整個序列非遞增），返回
false，並 reverse 整個序列變最小
- 從右向左找第一個
a[j] > a[i] 的位置 j
- 交換
a[i] 和 a[j]
- 將
[i+1, end) 區間 反轉（原為非遞增，反轉後變非遞減，即最小）
3. 圖解示例：1 2 3 → 1 3 2
初始：1 2 3 (最小)
步驟1：從右找 a[i]a[i] → j=2 (3>2)
步驟3：交換 → 1 3 2
步驟4：反轉 [i+1,end) → 區間只有 2，不變
結果：1 3 2 (下一字典序)
4. 完整枚舉示例
int a[] = {1, 2, 3}; // 必須從最小排列開始
do {
for (int x : a) std::cout << x << ' ';
std::cout << '\n';
} while (std::next_permutation(a, a+3));
/* 輸出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
⚠️ 必須從升序（最小字典序）開始，否則只能枚舉當前到最大之間的排列。
5. prev_permutation：逆向枚舉
- 從最大排列（降序）開始
- 生成上一字典序排列
- 同理：找
a[i] > a[i+1]、找 a[j] < a[i]、交換、反轉後綴
int a[] = {3, 2, 1}; // 最大排列
do { ... } while (std::prev_permutation(a, a+3)); // 產生所有排列（逆序）
6. 時間複雜度與應用
- 單次調用：O(N)
- 全排列枚舉：O(N! × N)
- 應用：旅行商問題（TSP）、八皇后、密碼破解、組合優化搜索
7. 自定義比較器
std::vector<std::string> v = {"b", "a", "c"};
std::sort(v.begin(), v.end(), std::greater<>()); // 降序初始化
do { ... } while (std::next_permutation(v.begin(), v.end(), std::greater<>()));
總結
next_permutation 以「最小增量字典序遞增」為核心邏輯，支點交換 + 後綴反轉 是關鍵步驟。記住：從最小排列開始、用 do-while 循環、需雙向迭代器。掌握其原理可手寫全排列生成器、解決排列組合類算法題。
