pythonでジェネレータを使って順列を小さい順に出力してみる

@shinoutです。
こないだ、phperのためのGAE勉強会に行ってきて、python学んできました。
そんなわけでpythonでジェネレータを使って何か書いてみようと思い、
1-nまでの数字の順列を小さい順に出力するプログラムを書いてみました。

ええと、たとえば
3 を入れると
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
が for文で取得できるような感じです。

#-*- coding: utf-8 -*-
def order(k): 
    # 1-kまでの数字リストを小さい順に出力する。

    def orderGenerator(li):
        # 1-kまでのリストを引数にとり、それらを小さい順に出力してゆくジェネレータ
        n = len(li);
        def order0(li):
            # 再帰の初期値のための関数。
            yield li
            raise StopIteration

        def order1(li):
            # 再帰ロジック。
            defaultLi = li[:] # もともといれてくれた配列
            haveToPop = 0 # popするべきインデックス位置
            while haveToPop < n:
                li = [ defaultLi[haveToPop] ] + defaultLi[:haveToPop] + defaultLi[haveToPop+1:] 
                # ここでliは、haveToPop == 3 で[3,1,2,4]、 haveToPop == 4 で[2,1,3,4]とかになってる。
                o = orderGenerator(li[1:])
                for childLi in o:
                    li[1:] = childLi
                    yield li
                haveToPop = haveToPop+1
            raise StopIteration(li)

        return eval("order%s(li)" % min(n, 1)) # order0 か order1 を呼び出す。
    return orderGenerator(range(1,k+1))

o = order(4)
for li in o:
    print li

ジェネレータの再帰、というロジックは結構ありそうですね。