std::next_permutation

定義於標頭檔案 `<algorithm>`
template< class BidirIt > bool next_permutation( BidirIt first, BidirIt last );	(1)	(C++20 起為 constexpr)
template< class BidirIt, class Compare > bool next_permutation( BidirIt first, BidirIt last, Compare comp );	(2)	(C++20 起為 constexpr)

將範圍 [first, last) 變換為下一個排列。若存在這樣的“下一個排列”，則返回 true；否則將範圍轉換為字典序最小的排列（如同透過 std::sort），並返回 false。

1) 所有排列的集合在字典序上按 operator<(C++20 前)std::less{}(C++20 起) 排序。

2) 所有排列的集合在字典序上按 comp 排序。

若 *first 的型別不可交換 (Swappable)(C++11 前)BidirIt 不是可值交換 (ValueSwappable)的(C++11 起)，則行為未定義。

first, last	-	定義要排列的元素範圍的迭代器對
comp	-	比較函式物件（即滿足比較 (Compare)要求，若第一個引數“小於”第二個則返回 true 的物件）。比較函式的簽名應等效於以下內容 bool cmp(const Type1& a, const Type2& b); 儘管函式簽名不需要有 const&，但函式不能修改傳遞給它的物件，並且必須能夠接受 `Type1` 和 `Type2` 型別（可能為 const）的所有值，而不管其值類別（因此，不允許 Type1&，除非對於 `Type1`，移動等效於複製，否則也不允許 Type1(C++11 起)）。型別 Type1 和 Type2 必須使得型別為 BidirIt 的物件可以被解引用，然後隱式轉換為兩者。
型別要求
- `BidirIt` 必須滿足舊式雙向迭代器 (LegacyBidirectionalIterator)的要求。

[編輯] 返回值

若新排列在字典序上大於舊排列，則為 true。false 若已到達最後一個排列且範圍被重置為第一個排列。

[編輯] 複雜度

給定 $\scriptsize N$ $N$ 為 std::distance(first, last)

1,2) 最多

N 2

次交換。

[編輯] 異常

迭代器操作或元素交換丟擲的任何異常。

[編輯] 可能的實現

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    auto r_first = std::make_reverse_iterator(last);
    auto r_last = std::make_reverse_iterator(first);
    auto left = std::is_sorted_until(r_first, r_last);
 
    if (left != r_last)
    {
        auto right = std::upper_bound(r_first, left, *left);
        std::iter_swap(left, right);
    }
 
    std::reverse(left.base(), last);
    return left != r_last;
}

[編輯] 注意

在所有排列序列的平均情況下，典型實現每次呼叫使用大約 3 次比較和 1.5 次交換。

當迭代器型別滿足舊式連續迭代器 (LegacyContiguousIterator)且其值型別的交換既不呼叫非平凡的特殊成員函式也不呼叫透過ADL找到的 swap 時，實現（例如 MSVC STL）可能會啟用向量化。

[編輯] 示例

以下程式碼列印字串 "aba" 的所有三個排列。

執行此程式碼

#include <algorithm>
#include <iostream>
#include <string>
 
int main()
{
    std::string s = "aba";
 
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
 
    std::cout << s << '\n';
}

輸出

aba
baa
aab

[編輯] 參閱

is_permutation (C++11)	確定一個序列是否是另一個序列的排列 (函式模板) [編輯]
prev_permutation	生成元素範圍的下一個更小的字典序排列 (函式模板) [編輯]
ranges::next_permutation (C++20)	生成元素範圍的下一個更大的字典序排列 (演算法函式物件)[編輯]

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作