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

{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 入門