std::next_permutation|C++|順列
std::next_permutation
という関数を覚えたのでメモ
std::next_permutation
は、[first, last) の範囲を次の順列に変換する関数です。*1
これを使うと配列内の要素の順列を簡単に列挙することができます。
全ての順列を取得する場合は、関数に最初に与える範囲が昇順にソート済みになっている必要があります。
全列挙例
#include <bits/stdc++.h> using namespace std; int main() { vector<int> v{ 1, 2, 3 }; //要素は昇順にソートしておく for( int i = 0; i < 6; ++i ) { for( auto &x : v ) { cout << x << " "; } cout << endl; next_permutation( begin( v ), end( v ) ); //次の順列が生成される } return 0; }
出力
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
std::next_permutation
については下記サイトで解りやすく説明されています。
参考:順列生成 next_permutation, prev_permutation 入門