Pastable version of Breadth first cartesian product iterator

<pre class='prettyprint' language='python'>from itertools import product
def breadth_first_product(*args):
	&quot;&quot;&quot;Works like itertools.product but iterates &quot;breadth first&quot;.
	breadth_first_product(&quot;abc&quot;, &quot;123&quot;) =&gt; a1 b1 a2 b2 c1 c2 a3 b3 c3&quot;&quot;&quot;

iters = map(iter, args)
	values = [[i.next()] for i in iters]
	yield tuple(a[0] for a in values)

depth = 1
	maybe_more = True
	while maybe_more:
		maybe_more = False		
		for advance_index in range(len(args)):
			try:
				values[advance_index].append(iters[advance_index].next())
				maybe_more = True
			except StopIteration:
				continue
			# A 1 bit in mask means we use the latest value, a 0 means we use 
			# all the values except the latest.
			mask = 1 &lt;&lt; advance_index
			while mask &lt; 2&lt;&lt;advance_index:
				lists = [v[:depth] if (mask&gt;&gt;i)&amp;1==0 else v[depth:depth+1]
						for i,v in enumerate(values)]
				dm = sum([1&lt;&lt;i for i,v in enumerate(lists) if len(v)==0])
				if dm != 0:
					# Optimization: Skip dm loops where one of the
					# lists is empty
					mask += dm
				else:
					for p in product(*lists):
						yield p
					mask += 1
		depth += 1</pre>
<a href="http://www.refactormycode.com/codes/1969-breadth-first-cartesian-product-iterator" style="color:#fff" title="As seen on RefactorMyCode.com"><img alt="Small_logo" src="http://www.refactormycode.com/images/small_logo.gif" style="border:0" /></a>

Refactor :my => 'code'

Recent

Popular

Pastable version of Breadth first cartesian product iterator