pythonでの順列全探索

概要

atcoderなどで順列全探索の問題が出た際に、さらっと参照するための記事です。
細かな順列全探索の説明は、アルゴリズムの解説サイトなどを見た方が良いと思います。

順列全探索について

順列全探索とは、ある集合{1,2,3,...,N}を並び替えた際にありうる全てのパターンを探索する方法です。
（おそらく）高校数学の確率などを求める際に倣ったPやCのPの方です。
細かな式の確認やPもCも記憶にない方はこちらの記事などをご参考ください。

例えば、N個の数列を並び替える際の並び替えの総数は**N！**通りですが、このN！通りのパターンを列挙してから行う全探索のことを順列全探索と呼んでいるそうです。

使い方

Pythonでは、itertoolsという非常に素敵なモジュールがあるため、そちらを用いるのが良いと思います。
（Python以外でも "言語名　順列" などで検索すれば、順列の求め方は出てくると思います。）

使い方は非常に簡単で、

example.py

import itertools
arr = [0, 1, 2]

print(list(itertools.permutations(arr)))
# [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

とpermutationsの引数に配列を渡すだけでできてしまいます。
※ぜひ上記だけでなく公式ドキュメントもご確認ください。

それでは、以下の問題を解く過程で、実際の利用方法を見ていきたいと思います。

引用元：Atcoder Beginner Contest 145

上の問題は、

1. 各座標を１回ずつ順にたどっていく。
2. 辿る際の各座標間の距離（移動距離）の和を求める。
3. この和を経路を辿るパターン全てで求め、その平均を出力する。
   と解釈できるので実装していきます。

入力

N
x1 y1
:
xN yN

sample.py

# ルートを使うため、今回はmathもインポートする
import itertools
import math

# 入力からNを受け取る 
N = int(input())

# 座標を全て格納する 
point = []
for _ in range(N):
  xy = list(map(int, input().split()))
  point.append(xy)
 
# 0 ~ N-1までの配列を作成
num = list(range(N))
 
# 街の番号の順列を全て列挙する
ptn = list(itertools.permutations(num))
 
# 合計の距離を格納する変数を定義
sum_dist = 0

# 各パターンごとに距離を求め、sum_dist に加算
for p in ptn:
  for i in range(len(p)-1):
    a = p[i]
    b = p[i+1]
    x1 = point[a][0]
    y1 = point[a][1]
    x2 = point[b][0]
    y2 = point[b][1]
    sum_dist += math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
 
# 加算したものを全パターンの総数で割ったもの（平均）を出力
print(sum_dist/len(ptn))

終わりに

順列を求める問題では、順列全列挙は非常に強力な手段です。
しかし、n個の集合の順列は、nの階乗の計算量になるため、利用できるのは、nが小さいor小さく設定できる時のみという点だけ注意しましょう。

※n = 10でも、10! = 3628800 ~ 10^6 のオーダーになります。

なんとなく理解できた方には、@e869120さんが書かれた分野別　初中級者が解くべき過去問精選 100 問で練習すると良いと思います。

ここまで、お読みいただきありがとうございました。