順列(n!)の全探索

2019年12月2日探索順列

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

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

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

アルゴリズム

順列の全探索：

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

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

※ 自身で実装する場合は、再帰関数を利用すると生成できます。

問題とプログラム例

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

入力：3
出力：
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

C++ の例

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

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

#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 = {0,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;
}

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("")

練習問題

探索順列