初めに

アルゴリズムの学習中をしていて順列全探索を覚えたのでアウトプットとして記事を書いています。
まだまだ浅学の身ですので、誤りがあればどんどんご指摘ください。

順列全探索とは

ある異なる要素を含むリストについてその要素を並べ替えたリストを全て列挙する全探索の手法です。
例えば、[1,2,3]を順列全探索すると[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]の６通りの順列を得ます。

実装例

permutations.rb

from itertools import permutations
list=[1,2,3]
per=permutations(list,2)
for i in per:
    print(i)

出力

ans.py

(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

ポイント

・ライブラリのitertools.permutationsを用いて順列を生成する。
・permutationsはイテレータであるため、そのままでは出力できない。
例えば、上記のコードでprint(per)としても出力されない
・permutationsの第二引数に数字を指定することでその個数だけ含まれた順列を生成できる

競プロ例題

https://atcoder.jp/contests/abc150/tasks/abc150_c

順列全探索が理解できる初心者向けの良問です。
ここでindex関数の使い方もおぼえてしまいましょう