競プロの基本事項確認~順列生成の方法~

この記事で解説したAtCoder073のD問題においてn!(n<=8)通りの順列を生成してそのそれぞれについて操作を行うという問題がありました。順列生成はAtCoderで良く出ますが、書き方を忘れがちなのでここでまとめておきます。

#[1]Pythonの場合
itertoolsモジュールにあるpermutationsを用います。
ここでは0~3が入った配列についてその順序を並べ替えた順列を全て生成させて考えます。

>>> import itertools
>>> t=[i for i in range(4)]
>>> itertools.permutations(t)
<itertools.permutations object at 0x104dc0af0>
>>> list(itertools.permutations(t))
[(0, 1, 2, 3), (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1), (0, 3, 1, 2), (0, 3, 2, 1), (1, 0, 2, 3), (1, 0, 3, 2), (1, 2, 0, 3), (1, 2, 3, 0), (1, 3, 0, 2), (1, 3, 2, 0), (2, 0, 1, 3), (2, 0, 3, 1), (2, 1, 0, 3), (2, 1, 3, 0), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 0, 2, 1), (3, 1, 0, 2), (3, 1, 2, 0), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> list(itertools.permutations(t,2))
[(3, 2), (3, 1), (3, 0), (2, 3), (2, 1), (2, 0), (1, 3), (1, 2), (1, 0), (0, 3), (0, 2), (0, 1)]

上記のようにイテラブルなオブジェクトである配列(permutationsの第一引数はイテラブルなオブジェクト)の順序を並べ替えてタプルに格納した順列の全通りが生成されているのが見てとれます。
また、permutationsの第二引数では$ _n P _r $の式におけるrを指定することができます(デフォルトではr=nで、ここではr=2より$ _n P _2 $が求まります。)。

#[2]C++の場合
algorithmライブラリにあるnext_permutationを使います。
ここでも0~3が入った配列についてその順序を並べ替えた順列を全て生成させて考えます。
Pythonでは順列を全て生成して考えていましたが、C++では昇順ソートしたものを初めの順列としてnext_permutation関数を適用することでその次の順列を生成するという方法をとります。そして、next_permutation関数を適用する順列が最後の順列(降順ソートしたもの)であった場合、初めの順列へと戻ります。また、このとき、next_permutation関数を適用する順列が最後の順列でない場合はfalseを最後の順列の場合はtrueを返すのでその返り値を利用してdo-while文を用いることで全ての順列に対してなんらかの操作をすることができます。
さらに、do-while文を用いる場合は最初の順列から始めないと全ての順列に対する操作ができませんが、順列が何通りあるかをあらかじめ計算しておけばその回数分だけnext_permutation関数を適用することで全ての順列に対してなんらかの操作をすることができます。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  int n=4;
  vector<int> v(n);
  //1刻みで格納できる関数、便利
  iota(v.begin(), v.end(), 0);
  do{
    //vは次の順列になる
    for(int i=0;i<n;i++){
          //なんらかの操作
    }
  }while(next_permutation(v.begin(),v.end()));
}

#[3]まとめ
PythonとC++それぞれの場合の順列生成について最後に重要な点をまとめておきます。

①Pythonの場合
・itertoolsモジュールのpermutationsを使う
・全通りの順列をタプルで生成する(非破壊的)
・それぞれの順列にはfor文でアクセスする

②C++の場合
・algorithmライブラリのnext_permutationを使う
・次の順列に置き換える(破壊的)
・昇順ソートした順列から始めるときはdo_while文でアクセス
　それ以外の順列から始めるときは順列の数を計算してfor分でアクセス