itertools.permutations

python

itertoolsのドキュメントを読んでいてpermutationsのコードの動きがよくわからなかったので調べてみた。

とりあえず、0から3までの数字の列を例に考えてみる。

[0 1 2 3]から始めて、0番目の数字(0)と1番目の数字(1)を交換、0番目の数字(1)と2番目の数字(2)を交換、0番目の数字(2)と3番目の数字(3)を交換という操作をすると次のように並び方が変化する。このとき得られる各配列は、0番目の数字が先頭にあるものの中で最小になっている。

0 1 2 3 # 初期値　　　0が先頭にくる配列の中で最小。
1 0 2 3 # 0と1を交換。1が先頭にくる配列の中で最小。
2 0 1 3 # 1と2を交換。2が先頭にくる配列の中で最小。
3 0 1 2 # 2と3を交換。3が先頭にくる配列の中で最小。

また、最後に得られた配列の先頭の数字を末尾に移動して、左に一つずつずらすともとの[0 1 2 3]という並び方にもどる。

同様のことは、要素が互いに異なっていて昇順にならんでいるならば成り立つので、0番目の数字を固定して、1番目より後ろに対しても同様のことができる。

0 | 1 2 3 # 初期値      0 1が先頭にくる配列のなかで最小。
0 | 2 1 3 # 1と2を交換。0 2が先頭にくる配列のなかで最小。
0 | 3 1 2 # 2と3を交換。0 3が先頭にくる配列のなかで最小。

0 1 2 3 # 1文字目より後ろを左回転。

1 | 0 2 3 # 0と1を交換。1 0が先頭にくる配列のなかで最小。
1 | 2 0 3 # 0と2を交換。1 2が先頭にくる配列のなかで最小。
1 | 3 0 2 # 2と3を交換。1 3が先頭にくる配列のなかで最小。

...

0、1番目の数字を固定して、2番目以降の文字に対して同様にすると、この場合全ての順列が得られる。

0 1 | 2 3 # 初期値      0 1 2が先頭にくる配列のなかで最小。
0 1 | 3 2 # 2と3を交換。0 1 3が先頭にくる配列のなかで最小。

0 | 1 2 3 # 2文字目より後ろを左回転。

0 2 | 1 3 # 1と2を交換。0 2 1が先頭にくる配列のなかで最小。
0 2 | 3 1 # 1と3を交換。0 2 3が先頭にくる配列のなかで最小。

0 | 2 1 3 # 2文字目より後ろを左回転。

0 3 | 1 2 # 2と3を交換。0 3 1が先頭にくる配列のなかで最小。
0 3 | 2 1 # 1と2を交換。0 3 2が先頭にくる配列のなかで最小。

...

ここまでをコードで書くと、次のようにforループが3つ入れ子になったものになる。

indices = [0, 1, 2, 3]
for i1 in range(4):
    indices[0], indices[i1] = indices[i1], indices[0]              
    for i2 in range(4-1):                                          # 0文字目は固定
        indices[1], indices[1+i2] = indices[1+i2], indices[1] 
        for i3 in range(4-2):                                      # 0、1文字目は固定
            indices[2], indices[2+i3] = indices[2+i3], indices[2] 
            print indices
        indices[2:] = indices[3:] + indices[2:3]                   # 2文字目より後ろを回転
    indices[1:] = indices[2:] + indices[1:2]                       # 1文字目より後ろを回転
indices[0:] = indices[1:] + indices[0:1]                           # 0文字目より後ろを回転

cyclesというループを回す回数を管理するリストを使って、入れ子を次のように書き換えると入力の長さが変わっても対応できるようになる。

indices = [0, 1, 2, 3]
n = len(indices)
cycles = range(n, 1, -1)                                         # cycles = [4, 3, 2]

print indices
while True:
    for i in reversed(range(len(cycles))):
        cycles[i] -= 1
        if cycles[i] == 0:
            indices[i:] = indices[i+1:] + indices[i:i+1]         # i番目より後ろを回転
            cycles[i] = n - i                                    # カウントをリセット 
        else:
            j = n - i - cycles[i]
            indices[i], indices[i+j] = indices[i+j], indices[i]  # i+j は -cycles[i] とも書ける。
            print indices
            break   
    else:
        break                                                    # forが最後までまわったら、whileを抜けて終了。

大体の流れはこのような感じ。forループの書き換えはいろいろな所で使えそう。