Pythonで組み合わせ列挙を再帰関数を使って行う

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

の「6.2 全探索」で登場する再帰関数を使った組み合わせ列挙問題をPythonで実装してみた。

問題

以下のinput/outputを実現する関数を実装する。

input:組み合わせを列挙したい配列
output:input配列の中で組み合わせに含まれる要素の番地が1,含まれない要素の番地が0になった配列群を格納したリスト

コード

def make_combination(input_list):
    def rec(n):
        nonlocal S_list
        nonlocal combinations_list
        if n == len(input_list):
            print(S_list)
            combinations_list.append(list(S_list))
            return

        #①の分岐生成
        rec(n + 1)

        #②の分岐生成
        S_list[n] = 1
        rec(n + 1)

        S_list[n] = 0

    combinations_list = []
    S_list = [0 for i in range(len(input_list))]
    rec(0)
    return combinations_list

input_list = [1, 5, 7]
combibations_list = make_combination(input_list)
print(combibations_list)
#[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

解説になってない解説

最初に組み合わせを列挙したい配列と要素数が同じで全ての要素が0の配列を作成し、それに再帰関数を用いて次々変更を加えていって全ての組合わせを列挙し、それらをconbinations_listに格納して返却するというのが全体の流れ。

キモとなる再帰関数がややこしい。一応処理の流れっぽいものを図にしてみたが、分かりづらい。

コード中で①の分岐生成とコメントされている箇所で生成されたプロセスが下図の①、②の分岐生成とコメントがされている箇所で生成されたプロセスが下図の②に該当する。
水色の[0,0,1]といった配列は再帰関数実行実行時のS_list。
赤字の配列は結果として出力される組み合わせパターン。