4. next_permutation

最終更新日時(UTC):
が更新

履歴 編集

function template
<algorithm>

std::ranges::next_permutation(C++20)

namespace std::ranges {
  template <bidirectional_iterator I,
            sentinel_for<I> S,
            class Comp = ranges::less,
            class Proj = identity>
    requires sortable<I, Comp, Proj>
  constexpr next_permutation_result<I>
    next_permutation(I first,
                     S last,
                     Comp comp = {},
                     Proj proj = {}); // (1) C++20

  template <bidirectional_range R,
            class Comp = ranges::less,
            class Proj = identity>
    requires sortable<iterator_t<R>, Comp, Proj>
  constexpr next_permutation_result<borrowed_iterator_t<R>>
    next_permutation(R&& r,
                     Comp comp = {},
                     Proj proj = {}); // (2) C++20
}

概要

与えられた時点の[first, last)の範囲を起点の順列として、辞書順によるその次の順列を生成する。

効果

[first, last)の範囲を次の順列に変換する。 比較 invoke(comp,invoke(proj, *i),invoke(proj, *j)) によって辞書順に並んでいる全ての順列の集合があると仮定すると、次の順列が発見される。

順列の辞書順とは、同じ長さNの順列a, bがあった時、その最上位の項から見た時にai != biとなる最初のi番目の項について、ai < bi（もしくはcomp(ai, bi) == true）となる時にa < bとするように定めた順序のことである。例えばこれは、各項（ai, bi）が0 ~ 9の数であるとすれば、それらをそのまま並べて構成した数の通常の大小関係に等しい。

辞書順による次の順列とは、現在の順列（[first, last)）よりも（上記の意味の順序で）大きい順列のうち取り得る最小のもののことである。

戻り値

next_permutation_result {
  .in = last,
  .found = 次の順列が存在する場合は true、そうでなければ false,
}

計算量

高々(last - first)/2回の要素の交換

備考

全ての順列を取得したい場合は、この関数に最初に与える範囲が、昇順にソート済みになっていること。
順列の長さをN（N = last - first）とすれば、そのような順列はN!個存在する。

例

#include <iostream>
#include <vector>
#include <algorithm>

void print(const std::vector<int>& v)
{
  for (int x : v) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
}

int main ()
{
  // 昇順にソート済みの入力
  std::vector<int> v = {1, 2, 3};

  do {
    print(v);
  } while (std::ranges::next_permutation(v).found);
}

出力

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

関連項目

バージョン

言語

  • C++20

処理系

参照