順列(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_permutationalgorithm に含まれています。

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

Python の例

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

練習問題

探索順列