■

:[Python]続・再帰

再帰の勉強。
今日は順列の生成。
インスパイヤ先↓
お気楽 Python プログラミング入門：第３回再帰定義と高階関数
バックトラック法、つまり後戻り法。
行ってみて間違ってたら帰ればよい、的な方法。

numList = []

def permutation(n, m = 0):
    if n == m: 
        print numList
    else:
        for x in range(1, n+1):
            if x in numList:
                continue
            numList.append(x)
            permutation(n, m + 1)
            numList.pop()

def main():
    permutation(n = 3)


if __name__ == "__main__":
    main()

D:\workspace\Python\2-26>python permutation.py
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

当たり前だけどうまく動いている。
インスパイヤ先では、for文で書いたときとの対比が出ているが、確かにこの場合だと、再帰で書くとすごくすっきりする。
ちょっとずつ再帰のすごさが分かってきたかも。
でも、でもでも、グローバル変数が出てきたのが腹立つ。
なんかコードを汚された感があるなぁ。
これをグローバル変数使わずに書けないものか思案中。