読者です 読者をやめる 読者になる 読者になる

再帰的ジェネレータ

ジェネレータを再帰的に定義するっていう発想を知った.
面白そう!!っていうことで早速ためす.
n個の中からm個とってきた組み合わせを作るジェネレータを作ってみる

def perm_gen(seq, n=None, repeated=False):
    if n is None:
        n = len(seq)
    if n == 1:
        for x in seq:
            yield [x]
    else:
        for e in seq:
            sub = seq[:]
            if not repeated:
                sub.remove(e)
            for sub in perm_gen(sub, n - 1, repeated):
                yield [e] + sub

こんなんでました.
で,テスト

>>> pg = perm_gen([1,2,3])
>>> pg.next()
[1, 2, 3]
>>> pg.next()
[1, 3, 2]
>>> pg.next()
[2, 1, 3]
>>> pg.next()
[2, 3, 1]
>>> pg.next()
[3, 1, 2]
>>> pg.next()
[3, 2, 1]
>>> pg.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
StopIteration
>>> pg = perm_gen([1,2,3], repeated=True)
>>> pg.next()
[1, 1, 1]
>>> pg.next()
[1, 1, 2]
>>> pg.next()
[1, 1, 3]
以下略

おお,できてる!(*'ω')b

ついでに,リストを返しちゃうタイプ

def permutations(seq, n=None, repeated=False):
    if n is None:
        n = len(seq)
    result = set()
    if n == 1:
        result = [[x] for x in seq]
    else:
        for i in range(len(seq)):
            sub = seq[:]
            if not repeated:
                sub.remove(seq[i])
            sub = permutations(sub, n - 1, repeated)
            for j in range(len(sub)):
                temp = [seq[i]]
                temp.extend(sub[j])
                result.add(tuple(temp))
    return map(list, list(result))

一度集合(set)の中にいれてるのは,[1, 2, 2]が与えられえたときに,2つ[1, 2, 2]をが入っちゃうのを防ぐために入れてみた.
ジェネレータバージョンでは出ちゃう(ノД`)シクシク