順列(n!)の全探索

探索順列

\(n!\)通りの全探索を行いたい時に順列が用いられます。

順列(permutation)とは、n個のものを順番に並べるのは何通りあるかを考える問題です。n個全てを区別できるなら、\(n!\)通りの並べ方があります。

爆発的に計算量が増加するのが特徴で、\(n=10\)前後の計算に数秒かかってしまいます。(参考:計算量同士の比較と入力サイズによる比較)

アルゴリズム

機能が充実しているプログラミング言語には、順列の全ての場合を生成するライブラリがあることが多いです。

それゆえアルゴリズムとしては単純で以下のようになります。

  1. \(n!\)通りの順列を生成し、それぞれの場合について処理を行う

プログラム例

入力を\(n\)とした時に、\(0, 1, 2, …, n-1\)までの数について、全ての並べ方を1行ごとに出力するプログラムを考えてみましょう。

入力例1

3

出力例1(行ごとの順番は違くても良い)

0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0 

Python の例

Pythonにはitertoolsモジュールのpermutations()関数を用いることで順列を生成することができます。

import itertools
n = int(input())
lis = [x for x in range(n)] # 0からn-1までのリスト
permutations_lis = itertools.permutations(lis)# 全ての場合のリストを生成
# 以下出力
for one_case in permutations_lis: 
  for num in one_case:
    print(num, end=" ")
  print("")

C++ の例

C++ では配列やベクトルなどのコンテナを並び替えて、次の順列の並べ方にしてくれる、next_permutationalgorithm に含まれています。

全ての並べ方を一度に生成するのではないので、メモリ消費は抑えられますが、最初のコンテナは昇順にソートされている必要があります。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> one_case;
    for (int i = 0; i < n; i++) { // one_case = {1,2,3,...n-1} とする
        one_case.emplace_back(i);
    }
    do {
        for (auto num : one_case) {
            cout << num << " ";
        }
        cout << "\n";
    } while (next_permutation(one_case.begin(), one_case.end()));
    // 順列の最後になるまで one_case を並び替えながらループ
    return 0;
}

関連問題

探索順列

Posted by cs-learner