再帰的ジェネレータ
ジェネレータを再帰的に定義するっていう発想を知った.
面白そう!!っていうことで早速ためす.
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]をが入っちゃうのを防ぐために入れてみた.
ジェネレータバージョンでは出ちゃう(ノД`)シクシク