重複順列が倒せない
重複順列の話 その２
正直最初はもっと簡単な話だと思ってました。まさかシリーズ物になるとは……
まず 前回 の訂正・改良。
#[EvalPerm] def repeated_permutation(dimension, iterable): """ 順列生成ジェネレータ作成 dimension 次元数（リストの長さ） iterable リストの要素を取得するためのイテレータ/ジェネレータ """ a = ','.join(map(lambda i:'i%d' % i, xrange(dimension))) b = ' '.join(map(lambda i:'for i%d in %s' % (i, repr(iterable)), xrange(dimension))) #(1) return eval('((%s) %s)' % (a,b)) def repeated_permutation_n(dimension, n): """ 順列生成ジェネレータ作成 dimension 次元数（数列の長さ） n 数列の要素 (0〜n-1の整数を要素とする) """ return repeated_permutation(dimension, xrange(n))
#(1) のように repr を通すことで 文字列でもリストでもジェネレータでも、ほとんどの場合うまくいくようです。だいぶすっきり。
前回の例では repr を通さなかっため暗黙のうちに str() で変換され問題が起きていたようです。
ただし、マニュアル によると
repr(object)
オブジェクトの印字可能な表現を含む文字列を返します。これは型変換で得られる (逆クオートの) 値と同じです。通常の関数としてこの操作にアクセスできるとたまに便利です。この関数は多くの型について、 eval() に渡されたときに同じ値を持つようなオブジェクトを表す文字列を生成しようとします。
「生成しようとします」という微妙な言い回し。物によって失敗する可能性もあるかも知れないってこと？
確かに__repr__を変なオーバーライドされてたらまずいかもね。
正攻法でも考えてみる。
def print_repeated_permutation(dimension, n, buf): if dimension == 0: print buf return for i in xrange(n): buf[dimension - 1] = i print_repeated_permutation(dimension - 1, n, buf)
この手の問題、とりあえず印字すればOKだったりするんだよね。
でも出力される順列をプログラムでさらに扱う場合、ジェネレータを作りたいはず。
じゃあ、これをどうしたらジェネレータに出来るのか。それがどうにも難しい。
再帰と yield を同時に扱ったことが無いからかな……。
とりあえずこれは宿題にしておく
別解：イテレータなクラスを作ってみた。
#[IterClassPerm] class RepeatedPermutationN(object): """ 整数の重複順列生成 """ def __init__(self, dimension, n): self.dim = dimension self.buf = [0] * dimension self.buf[0] = -1 #(2) self.max_value = n - 1 self.i = 0 self.range_list = range(dimension) def increment(self): for self.i in self.range_list: if self.buf[self.i] < self.max_value: self.buf[self.i] += 1 break if self.i < self.dim - 1: self.buf[self.i] = 0 continue raise StopIteration() def next(self): self.increment() return self.buf def __iter__(self): return self
#(2)で -1 しているのは、初回 next コールで１番目の解がとばされるのを防ぐため。
next が返すのは内部バッファの参照なので外で変更したい場合はコピーをとらないとダメ。
任意の要素を列挙できるように拡張。
#[IterClassPerm] def _get_seq(obj): return [x for x in obj] class RepeatedPermutationA(RepeatedPermutationN): """ 任意要素の重複順列生成 A """ def __init__(self, dimension, iterable): self.values = _get_seq(iterable) super(RepeatedPermutationA, self).__init__(dimension, len(self.values)) def next(self): self.increment() return map(lambda x:self.values[x], self.buf) class RepeatedPermutationB(RepeatedPermutationN): """ 任意要素の重複順列生成 B """ def __init__(self, dimension, iterable): self.values = _get_seq(iterable) self.value_buf = [self.values[0] for i in xrange(dimension)] super(RepeatedPermutationB, self).__init__(dimension, len(self.values)) self.range_list = range(dimension) def next(self): self.increment() for i in self.range_list[:self.i+1]: self.value_buf[i] = self.values[self.buf[i]] return self.value_buf
RepeatedPermutationB は、self.buf と同じ要素数の self.value_buf を用意してそこに解となるリストを作っていく。前回のリストが残っているので次回 next コール時には、変更された要素だけの差分更新で済む。
実行例
>>> for x in RepeatedPermutationN(3,4): print x [0, 0, 0] [1, 0, 0] [2, 0, 0] [3, 0, 0] [0, 1, 0] [1, 1, 0] #以下略 >>> from itertools import izip >>> d = 3 >>> i = 'Hoge Fuga Moga'.split() >>> for x in izip(RepeatedPermutationA(d, i), RepeatedPermutationB(d, i)): print x (['Hoge', 'Hoge', 'Hoge'], ['Hoge', 'Hoge', 'Hoge']) (['Fuga', 'Hoge', 'Hoge'], ['Fuga', 'Hoge', 'Hoge']) (['Moga', 'Hoge', 'Hoge'], ['Moga', 'Hoge', 'Hoge']) (['Hoge', 'Fuga', 'Hoge'], ['Hoge', 'Fuga', 'Hoge']) (['Fuga', 'Fuga', 'Hoge'], ['Fuga', 'Fuga', 'Hoge']) (['Moga', 'Fuga', 'Hoge'], ['Moga', 'Fuga', 'Hoge']) (['Hoge', 'Moga', 'Hoge'], ['Hoge', 'Moga', 'Hoge']) (['Fuga', 'Moga', 'Hoge'], ['Fuga', 'Moga', 'Hoge']) (['Moga', 'Moga', 'Hoge'], ['Moga', 'Moga', 'Hoge']) (['Hoge', 'Hoge', 'Fuga'], ['Hoge', 'Hoge', 'Fuga']) #以下略
パフォーマンス測定なんかもやってみたいけど、今日はここまで。
その３へ続く。
