Pythonで順列全探索を実装してみる-ABC150
本記事では順列全探索をPythonで実装していきます。
Pythonではitertoolsを使うことで簡単に順列を生成することができます。
順列全探索とは
順列全探索とは通りの順列の組み合わせを全探索する手法です。
例えば、(1, 2, 3)の組み合わせはなので全部で9種類あります。
9種類の組み合わせはこのようになります。
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
順列は再帰関数を利用することによって自分で一から実装することもできますが、Pythonの場合は順列の組み合わせを生成するライブラリ(itertools)が存在するので、今回はこちらを利用します。
例題
今回は順列全探索の例題として以下の問題を取り扱います。
atcoder.jp
問題文
大きさ N の順列 ((1, 2, ..., N) を並び替えてできる数列) P, Qがあります。
大きさ Nの順列は N! 通り考えられます。このうち、P が辞書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、|a−b|を求めてください。
2つの数列 X, Y について、ある整数 k が存在してかつ
が成り立つとき、X は Y より辞書順で小さいと定義されます。
制約
2≤N≤8
P, Qは大きさ Nの順列
入力は全て整数
実装
この問題はNの順列を辞書順に生成した後に、各P,Qのインデックスを取得することで簡単に解くことができます。
itertools.permutationsでNの全ての順列を生成することが出来れば、あとはインデックスの取得(index)と絶対値の計算(abs)で答えを導くことができます。
以下が実装したコードです。
#ABC150C import itertools n = int(input()) p = tuple(map(int,input().split())) q = tuple(map(int,input().split())) ls = list(itertools.permutations(range(1,n+1))) #順列生成 print(abs(ls.index(p)-ls.index(q)))
