順列を求める(2) - Mae向きなブログ

以前、「順列を求める - Mae向きなブログ」で自前で順列を求める関数を作ってみたのですが、「[C#] 順列を求める next_permutation() 代わりを実装する方法 │ Web備忘録」に順列を列挙する面白いアルゴリズムが紹介されていましたので、Pythonで作ってみました。

以下のようなアルゴリズムで順列を求めています。

隣り合う要素が昇順(a[i] < a[i+1])になっている一番大きい i を見つける
i が見つからないとき、全体が降順になっているので処理終了
末尾から順番に見て、a[i] より大きい要素のインデックス j を見つける
a[i] と a[j] を入れ替え、i+1以降の要素を反転する

例

1 4 3 2から2 1 3 4を生成する過程

(1) 1 4 3 2 
    i     
(2) iは見つかった！
(3) 1 4 3 2
    i     j
(4) 2 4 3 1 # a[i]とa[j]を入れ替え、
    2 1 3 4 # i+1以降の要素を反転する

`my_permutations.py`

実行

 % python my_permutations.py
4
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

参考