from itertools import product
def breadth_first_product(*args):
"""Works like itertools.product but iterates "breadth first".
breadth_first_product("abc", "123") => a1 b1 a2 b2 c1 c2 a3 b3 c3"""
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 << advance_index
while mask < 2<<advance_index:
lists = [v[:depth] if (mask>>i)&1==0 else v[depth:depth+1]
for i,v in enumerate(values)]
dm = sum([1<<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
Refactorings
No refactoring yet !
Ants
January 6, 2012, January 06, 2012 04:17, permalink
I'm confused... I maybe fixated on the term "Cartesian Product" since that is what itertools.product() is supposed to produce. I thought you were looking for a breadth first enumeration of the Cartesian product instead of the depth first results produced by itertools.product().
Here are the enumerations displayed graphically. (Please forgive the ASCII art.)
Cartesian product of {a, b, c} x { 1, 2, 3 }:
a b c
1 a1 b1 c1
2 a2 b2 c2
3 a3 b3 c3
Depth first enumeration:
a b c
1 a1 b1 c1
| / | / |
V ^ V ^ V
2 a2 | b2 | c2
| / | / |
V/ V/ V
3 a3 b3 c3
Breadth first enumeration:
a b c
1 a1->b1->c1
/
<-----
/
2 a2->b2->c2
/
<-----
/
3 a3->b3->c3
Ants
January 4, 2012, January 04, 2012 20:51, permalink
Your code doesn't seem to work correctly. Running the following:
>>> for x in breadth_first_product('abc', '123'):
... print x
Results in:
('a', '1')
('b', '1')
('a', '2')
('b', '2')
('c', '1')
('c', '2')
('a', '3')
('b', '3')
('c', '3')
which is not quite breadth first.
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:52, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:53, permalink
What should the output be according to you?
jjj
abrakadabra42.myopenid.com
January 4, 2012, January 04, 2012 21:55, permalink
Oh my god this site is crappy.
jjj
Ants
January 5, 2012, January 05, 2012 13:22, permalink
This site got crappy after Intridea picked it up, did a two-week long "SparkTime" () work on it and then after that seems to have left it to languish.
Anyway, if 'abc', '123' were really breadth first, the result should be:
('a', '1')
('b', '1')
('c', '1')
('a', '2')
('b', '2')
('c', '2')
('a', '3')
('b', '3')
('c', '3')
abrakadabra42.myopenid.com
January 5, 2012, January 05, 2012 17:49, permalink
That is what itertools.product produces if you change the order of the arguments. In my opinion that is depth first. It is exploring the whole "abc" path before going down even one step on the "123" path. But maybe we just have different terminology. Anyway, my function does seem to do what I want when I test it, it does not explore another level until it has returned all the combinations of the elements at previous levels.
London massage
January 8, 2012, January 08, 2012 23:50, permalink
This is a very useful script it is quite good and informative.
There must be an easier way to do this?