n段飛び

stairs_2.py

#!/usr/bin/env python

import functools

# メモ化を行うデコレータ
# 戻り値をキャッシュするのでprint()は使わないように
@functools.lru_cache()
def stairs(n):
    if n < 0:
        return None
    elif n == 0:
        return [[]]
    else:
        # 結果を返すリストを作成する
        ret = []
        #
        # n段飛びの全パターンは
        # - 1段飛んだ + n-1段飛びの全パターン
        # - 2段飛んだ + n-2段飛びの全パターン
        # - 3段飛んだ + n-3段飛びの全パターン
        # で列挙できる。
        #
        for i in range(1, 4):  # iは1, 2, 3の値を取る
            # n-i 段飛びの全パターンをresults変数に保存する
            results = stairs(n - i)
            # n-i 段飛びのパターンはNoneかもしれない
            # n = 2, i = 3なら n-i は -1で、この関数冒頭の通りNone
            # それは、無視する
            if results is not None:
                # 結果を返すリストに
                # - 1段飛んだ + n-1段飛びの全パターン
                # - 2段飛んだ + n-2段飛びの全パターン
                # - 3段飛んだ + n-3段飛びの全パターン
                # の全てを追加していく
                for result in results:
                    # iを先頭にしてresultsの中身をその後に並べたリスト。
                    # 例えば i が 3, resultが[1, 1, 2]なら
                    # ret.append([3, 1, 1, 2]) しているのと同じ。
                    # この*は「アンパック」と呼ばれる。
                    # わかり易さを重視するなら以下のようにしても良い
                    #
                    # tmp = [i]
                    # tmp.extend(result)
                    # ret.append(tmp)
                    #
                    ret.append([i, *result])
        return ret


if __name__ == '__main__':
    import sys
    if len(sys.argv) != 2:
        print('Usage: {} n'.format(sys.argv[0]))
        sys.exit(1)
    cache = {}
    for result in stairs(int(sys.argv[1])):
        print(','.join(str(i) for i in result))