◐ Shell
clean mode source ↗

std::prev_permutation - cppreference.com

提供: cppreference.com

<tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody>

ヘッダ <algorithm> で定義

(1)

template< class BidirIt > bool prev_permutation( BidirIt first, BidirIt last);

 (C++20未満)

template< class BidirIt > constexpr bool prev_permutation( BidirIt first, BidirIt last);

 (C++20以上)
(2)

template< class BidirIt, class Compare > bool prev_permutation( BidirIt first, BidirIt last, Compare comp);

 (C++20未満)

template< class BidirIt, class Compare > constexpr bool prev_permutation( BidirIt first, BidirIt last, Compare comp);

 (C++20以上)

範囲 [first, last) を operator< または comp について辞書的に順序付けされたすべての順列の集合の前の順列に変換します。 そのような順列が存在すれば true を返し、そうでなければ範囲を (std::sort(first, last); std::reverse(first, last); によって行われたかのような) 最後の順列に変換して false を返します。

引数

first, last - 置換する要素の範囲
comp - 第1引数が第2引数より小さい場合に true を返す、比較関数オブジェクト (Compare の要件を満たすオブジェクト)。

比較関数のシグネチャは以下と同等であるべきです。

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。

例外

イテレータの操作または要素の swap によって投げられるあらゆる例外。

計算量

多くとも (last-first)/2 回の swap。 順列のシーケンス全体を平均すると、一般的な実装では呼び出しあたりおよそ 3 回の比較と 1.5 回の swap を使用します。

実装例

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;
        }
    }
}

例

以下のコードは文字列 "abc" の6つの順列すべてを逆順に表示します。

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

出力:

関連項目