std::prev_permutation

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

將範圍 [first, last) 轉換為上一個排列。如果存在這樣的排列，則返回 true，否則將範圍轉換為最後一個排列（如同透過 std::sort 後跟 std::reverse），並返回 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` 必須滿足可值交換 (ValueSwappable)和舊式雙向迭代器 (LegacyBidirectionalIterator)的要求。

[編輯] 返回值

如果新排列在字典序上先於舊排列，則為 true。如果達到了第一個排列並且範圍被重置為最後一個排列，則為 false。

[編輯] 異常

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

[編輯] 複雜度

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

1,2) 最多

N 2

次交換。

[編輯] 可能的實現

template<class BidirIt>
bool prev_permutation(BidirIt first, BidirIt last)
{
    if (first == last)
        return false;
    BidirIt i = last;
    if (first == --i)
        return false;
 
    while (1)
    {
        BidirIt i1, i2;
 
        i1 = i;
        if (*i1 < *--i)
        {
            i2 = last;
            while (!(*--i2 < *i))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
 
        if (i == first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

[編輯] 註解

平均而言，在整個排列序列中，典型實現每次呼叫大約使用 3 次比較和 1.5 次交換。

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

[編輯] 示例

以下程式碼以逆序列印字串 "cab" 的所有六種排列。

執行此程式碼

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

輸出

cab bca bac acb abc cba

[編輯] 參閱

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

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

cppreference.com

名稱空間

變體

檢視

操作