n回のループの一般形はどう書けるのか？

Python

以下はoceanさんの解答にコメントを付けたものである。

def cross_product(*a):
    stack = []
    def traverse(i):
        if i == len(a):  # 再帰では、終了条件が必要
            yield stack[:]
        else:
            for x in a[i]:
                stack.append(x)
                # 以下のtraverse()は関数呼び出しではなく、ジェネレータの作成なのでforループを使う必要がある
                for the_stack in traverse(i + 1):
                    yield the_stack
                stack.pop()  # バックトラックする必要がある
    return traverse(0)

def print_cross_product(*a):
    for b in cross_product(*a):
        print b
    print

def main():
    print_cross_product([1,2,3,4], "abc")
    print_cross_product([0, 1], "ab", ["Foo", "Bar"])

if __name__ == '__main__':
    main()

上記の方法は、以下のループを再帰を利用して、一般形に対応した方法である。

for i in [1,2,3,4]:
    for j in 'ab':
        print [i, j]

for i in [0,1]:
    for j in 'ab':
        for k in ['Foo', 'Bar']:
            print [i, j, k]

再帰を使った方法では、以下の3つの要素が盛り込まれている。

  1. 終了条件
  2. ループ1回分の処理
  3. ループごとに条件を変化させる部分

3つ目は重要でないかもしれないが、ジェネレータならさらにfor文と組み合わせるという実装のテクニックも使う必要がある。ここで議論したいことは、2つ目の例のような簡単な処理がしたいのに、再帰を使った実装は理解するのに難しいし、for文を使ったループでも一般化すると難しいということだ。もっと簡単に分かりやすく一般化できないだろうか。itertoolsを使って色々考えているが、n回のループに対応した簡単な実装が思いつかない。問題提起はできたのでもう少し研究してみるつもり。


追記：

一応できたが、余計分かりにくくなった。islice、izip、cycle、調整のために作成した関数slow_listを組み合わせればできた。結局、izipがポイントかもしれない。izipは n 個のリストを1つのタプルのリストにしてくれる。とりあえずの結論としては、複雑なロジックなので複雑な実装になったというところだろうか...。

from itertools import *

def foo(*L):
	def muls(seq):
		return reduce(int.__mul__, seq)
	lens = map(len, L)
	nums = [muls(lens[i+1:] + [1]) for i, l in enumerate(L)]
	nrep = muls(lens)
	def slow_list(lst, n):
		return chain(*[islice(l, n) for l in imap(repeat, lst)])
	for i in islice(izip(*[cycle(slow_list(l, nums[i])) for i, l in enumerate(L)]), nrep):
		print i

foo([1,2,3,4], 'abc')
print 
foo([0,1], 'ab', ['Foo', 'Bar'])