Pythonでパターンの列挙

背景

AtCoder Beginner Contest 150のC問題で重複なしで辞書順に並び替える方法がわからなかった。
調査、動作確認した内容を残しておく。

itertools

効率的なループ実行のためのイテレータ生成関数であるitertoolsを使用する。標準ライブラリなのでinstallは不要。
itertoolsは下記の3種類のイテレータが存在する。

• 無限イテレータ
• 一番短いシーケンスで止まるイテレータ
• 組み合わせイテレータ

今回は、その中で組み合わせイテレータの中のメソッドの1つであるpermutationsを用いる。

参考までに組み合わせイテレータを下記にまとめておく。
その他の2種類に関しては、数が多いので割愛する。(今後何度も使用する機会があり、自分の記憶への定着が悪い場合は追記するかもしれない)

メソッド	結果
product	重複ありの順列
permutations	重複なしの順列
combinations	重複ありの組み合わせ
combinations_with_replacement	重複なしの組み合わせ

動作確認

import itertools

n = 3
l = list(range(1,n+1)) # [1, 2, 3]
permutations = list(itertools.permutations(l)) # [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
p = (2, 3, 1) # listではなくtuple
permutations.index(p) # 3