【c++】配列やリストの順列を取得【next_permutation】

yamagenii 49views 更新:2016年7月25日

ある配列やリストが与えられた時の順列を生成するということを考える

{1, 2, 3} という要素列があった時の順列は

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

で与えられる。

C++であればこれを簡単にstd::next_permutationを使用することで得られる

リスト時

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    const int N = 3;
    vector<int> v(N);
    iota(v.begin(), v.end(), 1);
    do {
        for(auto x : v) cout << x << " "; cout << "\n";
    } while( next_permutation(v.begin(), v.end()) );
    return 0;
}

配列時

#include <iostream>     
#include <algorithm>    
using namespace std;
int main () {
  int myints[] = {1,2,3};
  sort (myints,myints+3);
  do {
    cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( next_permutation(myints,myints+3) );
  return 0;
}

Nに対してN!通りなのであまりにもNが大きい場合は使用すると処理量がすごいことになるので注意


cplusplus.com 順列生成 next_permutation, prev_permutation 入門

ログイン / 新規登録してコメントする

このソースコードをストックして後で利用したり、作業に利用したソースコードをまとめることができます。

こちらもお役に立つかもしれません