続続☆重複順列

Python

重複順列の話 その３


前回のイテレータクラスを見てて、なんかまた別のジェネレータに出来そうだと思った。
それで出来たのがこれ。

#[NonRecurseGenPerm]
def repeated_permutation_n(dimension, n):
    buf = [0] * dimension
    max_val = n - 1
    max_dim = dimension - 1
    range_list = range(dimension)
    while True:
        yield buf
        for i in range_list:
            if buf[i] < max_val:
                buf[i] += 1
                break
            if i < max_dim:
                buf[i] = 0
                continue
            return

def repeated_permutation_a(dimension, iterable):
    values = _get_seq(iterable)    # _get_seq は前回参照
    for L in repeated_permutation_n(dimension, len(values)):
        yield map(lambda i:values[i], L)

def repeated_permutation_b(dimension, iterable):
    values = _get_seq(iterable)
    value_buf = [values[0] for i in xrange(dimension)]
    buf = [0] * dimension
    max_val = len(values) - 1
    max_dim = dimension - 1
    range_list = range(dimension)
    i = 0
    while True:
        for j in range_list[:i+1]:
            value_buf[j] = values[buf[i]]
        yield value_buf
        for i in range_list:
            if buf[i] < max_val:
                buf[i] += 1
                break
            if i < max_dim:
                buf[i] = 0
                continue
            return


それぞれ、前回のイテレータクラス RepeatedPermutationN,A,B をジェネレータにしたもの。
そういえば、ジェネレータ構文ってイテレータを簡単に作れるようにするって目的を持っていたっけ。
それにしても固定長バッファをごにょごにょしていると「あー俺って手続き脳だなぁ」と思い知らされる。
関数名がかぶるのでモジュールを分けることにしました。一行目がモジュール名。後でまとめてパフォーマンステストする予定。

本命!! 再帰 + yield でジェネレータ

前回保留にした、再帰とyieldを使ったジェネレータ構文ですが、結局 web で見つけてしまいました。

M.Hiroi's さん家の「お気楽 Python プログラミング入門」:●ジェネレータ関数の再帰定義より転載。

def gen_perm(nums, n = 0):
    if n == len(nums):
        yield []
    else:
        for x in gen_perm(nums, n + 1):
            for y in nums:
                if y not in x:
                    yield x + [y]  #(1)


そうそう、まさにやりたかったこと！
「再帰関数がサブシーケンスを返して、それに１要素追加して上へ返す」ってのは分かてたんですけど、
#(1) のところが思い付けなかったみたいです。
このサイト勉強になるサイトで、昔 xyzzy lisp 覚えるのにお世話になりました。
やっぱり、lisp脳はエレガントだな〜。


で、上は重複の無い順列で、次元数（リストの長さ）が指定できないので、これまでのプログラムに合わせて改造させていただきました。

#[RecurseGenPerm]
def repeated_permutation(dimension, iterable, n=0):
    if n == dimension:
        yield []
    else:
        for subseq in repeated_permutation(dimension, iterable, n + 1):
            for item in iterable:
                yield subseq + [item]

ふう、これでもう思い残すことは無い。


といつつその4へ続く。