全ての組み合わせ in Python DouKaku?

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

普通に再帰で。（二番目の例の答えが違うけど、これでいいんですよね？）

def cross_product(*a):
    stack = []
    def traverse(i):
        if i == len(a):
            yield stack[:]
        else:
            for x in a[i]:
                stack.append(x)
                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()

ちょうど、一つ前のお題で任意の個数からなるBool値のタプルの
組み合わせを生成するのに、同じようなコードを書きました。

余談ですが「コード：」のテキストボックスのフォントが、等幅だとうれしいのですが。

def CP(*l):
  def f(l):
    return ([a] + x for a in l[0] for x in f(l[1:])) if len(l) > 1 else ([a] for a in l[0])
  return f(l)

print CP([1,2,3,4], "abc")
print CP([0, 1], "ab", ["Foo", "Bar"])

おっと、ジェネレータは単にprintしてもダメだった。

ちょっとだけ修正。

def CP(*l):
  def f(l):
    return ([a] + x for a in l[0] for x in f(l[1:])) if len(l) > 1 else ([a] for a in l[0])
  return f(l)

print list(CP([1,2,3,4], "abc"))
print list(CP([0, 1], "ab", ["Foo", "Bar"]))

再帰とfor文を使わずに一気に組み合わせを作成。
11行目のfor文はジェネレータから要素を取り出す処理として使用。ここはもちろん、return list(islice(...))とすればfor文を消せる。
12行目をyield iとすればcross_productがジェネレータになる。

もともと、"n次のforループを一般化"しようと考えて作成したが、かなり分かりづらくなった。
再帰もfor文も使わず簡単に書ける何かうまい方法ないのだろうか。

ちなみに、slow_listは以下のようになる。
>>> list(slow_list([1,2,3,4], 3))
[1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]

from itertools import *

def cross_product(*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

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

なるほど、stackって何に使うのかと思ったのですが
stackに入れたり出したりして値のペアを作り
コピーして返しているんですね。

速いのかな、と調べてみたのですが[1,2,3,4], "abc"のデータでは
下の書き方の方が40%くらい速かったです。
(1万回繰り返しで0.34と0.20)
# いまいち納得のいかない結果…

def cross_product2(*args):
	if not args:
		yield []
	elif len(args) == 1:
		for x in args[0]:
			yield [x]
	else:
		for x in args[0]:
			for y in cross_product2(*args[1:]):
				yield [x] + y

引数をrange(10), range(10)と増やしてみると、元のが2.00秒、新しいのが1.05秒と差が広がりました。

逆にrange(3), range(3), range(3), range(3)と深くしてみたところ元のが2.21、新しいのが2.11と僅差になりました。

appendとpopを繰り返すコストが、リストの加算で毎回新しく作ってしまうコストに比べてあんまり安くないんでしょう… なのであまり再帰呼び出しが深くない(掛け合わせる要素が多くない)場合には作ってしまう方が速い、と。

ちなみに下のように無駄な処理をループの外でやるようにしたところ0.16秒と92%の高速化になってしまいました。もちろんそのぶんメモリは食いますが…。

def cross_product2(*args):
	if not args:
		yield []
	elif len(args) == 1:
		for x in args[0]:
			yield [x]
	else:
		tails = cross_product2(*args[1:])
		for x in args[0]:
			head = [x]
			for tail in tails:
				yield head + tail

1
2
3

>>> from itertools import product
>>> list(product([1,2,3,4], 'abc'))
[(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'),  (3, 'c'), (4, 'a'), (4, 'b'), (4, 'c')]

DouKaku?

全ての組み合わせ

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq