ジェネレータで再帰的に組み合わせを返す

たとえば0 1からなるビット列の配列がほしいみたいなとき。組み合わせが少なければ愚直にやってもいいが、多いとき、ビット演算でやると文字列の扱いになって変換処理が時間的にボトルネックになり、リストで管理するとメモリ的にボトルネックになる。

ジェネレータで毎回帰ってきた値を処理できれば嬉しいと思うのでそうする。これですべての組み合わせみたいなよくあるパターンも処理できるわけ。next_permutation的なこともできるんじゃないの。しらんけど

def f(arr, limit):
    if len(arr) == limit:
        yield arr
    else:
        for i in [0, 1]:
            next_arr= arr[:]
            next_arr.append(i)
            for j in f(next_arr, limit):
                yield j

g = f([], 10)
count = 0
for x in g:
    print(x)
    count += 1
print("count: {}".format(count))  # 1024

nCr的な組み合わせ列挙ならこうやるねぼかぁ

def nCr(i, cur, rest, target):
    if rest == 0:
        yield cur
    elif len(target) - i == rest:
        # 今回のやつを取るしかない
        nex = cur[:]
        nex.append(target[i])
        for ncr in nCr(i+1, nex, rest-1, target):
            yield ncr
    else:
        # 含めるか含めないか
        nex = cur[:]
        nex.append(target[i])
        for ncr in nCr(i+1, nex, rest-1, target):
            yield ncr
        for ncr in nCr(i+1, cur[:], rest, target):
            yield ncr
        

arr = list(range(8))
g = nCr(0, [], 5, arr)
for x in g:
    print(x)

参考っぽいの

これは引数にリストで渡したやつの組み合わせを考えるやつ。

再帰とジェネレータ