重複順列生成 - evalで再帰いらず -

擬似多次元配列 の動作確認をしていて気になった。

>>> g = ((x,y,z) for x in range(2) for y in range(2) for z in range(2))
>>> for pos in g:
        print pos, ma[pos]

(0, 0, 0) 100
(0, 0, 1) -1
(0, 1, 0) -1
(0, 1, 1) -1
(1, 0, 0) -1
以下略

ma は三次元配列。インデクス値 0,1 の範囲で全要素を列挙する。
上のようにジェネレータ式で for を連ねれば難しいこと考えずに達成できる。
だけど問題は配列の次元数は可変だってこと。
もし十次元配列だったら、for を 10個も書くの？
それはあんまりだ。めんどくさ過ぎる。

普通は再帰で考える

どうみても再帰問題です。そのはずなんだけど、どうにも頭が回らない。上手くいかねー。
おかしいなぁ、昔Cで似たようなことやった記憶はあるんだけど。
どうでもよくなりかけた頃、ふとジェネレータ式を見て思いついた。

「そうかジェネレータ式で必要なだけ for を連ねればいいんじゃん！」
え？ ……それは面倒だったんじゃないかって？ いやいやつまり……

ジェネレータ式を文字列で作って eval すりゃいい

作るべきジェネレータ式はこんなかんじ。

((i0,i1,i2, ... id-1) for i0 in range(n) for i1 in range(n) for i2 in range(n) ... for id-1 in range(n))

次元数 d によって2箇所に可変部分があるけど、文字列操作と考えたら大したことは無い。
n は、インデクスの上限（開区間上限）。
数学的に言うと、重複順列の問題だったみたいなので、それっぽい名前で。

def repeated_permutation_n(dimension, n):
    a = ','.join(map(lambda i:'i%d' % i, xrange(dimension)))
    b = ' '.join(map(lambda i:'for i%d in xrange(%d)' % (i,n), xrange(dimension)))
    return eval('((%s) %s)' % (a,b))

数値以外も列挙したい

順列は別に数値に限った話ではないので、もう少し一般化してみる。

def repeated_permutation(dimension, iterable):
    if isinstance(iterable, str):
        iterable = iterable.replace('\\','\\\\').replace("'",r"\'")
        iterable = "'%s'" % iterable
    elif isinstance(iterable, unicode):
        iterable = iterable.replace(u'\\',u'\\\\').replace(u"'",ur"\'")
        iterable = u"u'%s'" % iterable
    a = ','.join(map(lambda i:'i%d' % i, xrange(dimension)))
    b = ' '.join(map(lambda i:'for i%d in %s' % (i,iterable), xrange(dimension)))
    return eval('((%s) %s)' % (a,b))

列挙される値を数値上限 n から iterable に変更。
iterable が str や unicode のときに若干細工が必要だった以外は特に変わったところ無し。

実行例

>>> for x in repeated_permutation_n(2,3):
	print x
	
(0, 0)
(0, 1)
(0, 2)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(2, 2)

>>> for x in repeated_permutation(3, 'AB'):
	print x
	
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'B', 'A')
('A', 'B', 'B')
('B', 'A', 'A')
('B', 'A', 'B')
('B', 'B', 'A')
('B', 'B', 'B')

重複順列の話 その２ へ続く。