GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing cpprefjp.github.io — std::ranges::prev_permutation - cpprefjp C++日本語リファレンス

リファレンス
algorithm
prev_permutation

最終更新日時: 2026年09月19日 21時31分51秒 (JST)
rotarymars が更新

履歴編集

function template

std::ranges::prev_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 prev_permutation_result<I>
    prev_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 prev_permutation_result<borrowed_iterator_t<R>>
    prev_permutation(R&& r,
                     Comp comp = {},
                     Proj proj = {}); // (2) C++20
}

概要

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

(1): イテレータ範囲を指定する
(2): Rangeを直接指定する

効果

[first, last)の範囲を前の順列に変換する。

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

戻り値

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

計算量

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

備考

全ての順列を取得したい場合は、この関数に最初に与える範囲が、降順にソート済みになっていること。

例

#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 = {3, 2, 1};

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

出力

バージョン

言語

C++20

処理系

Clang: 16.0.6 ✅
GCC: 10.1.0 ✅
Visual C++: 2019 Update 10 ✅

参照

N4861 25 Algorithms library
LWG Issue 3169. Ranges permutation generators discard useful information
- C++20で、ranges::next_permutation/ranges::prev_permutationの戻り値がboolから、順列生成後の終端イテレータも返す結果型に変更された

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

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

概要

効果

戻り値

計算量

備考

例

出力

関連項目

バージョン

言語

処理系

参照