I wrote the following recursive routine to compute cross product of two sets.
def combine(input1,input2,output):
if len(input2)==0:
return output
else:
for num in input1:
output.append((num,input2[0]))
combine(input1,input2[1:],output)
input1=[1 2 5]
input2=[2 3]
output=[(1,2), (1,3), (2,2),(2,3),(5,2),(5,3)]
Is it possible to make the recursion better, for example removing the loop in else and trying to do in same function. I'm looking at different ways of solving the problem.
Edit: Not looking for a solution with something in-built. Looking for how can I do recursion differently, and not use itertools.product.
The simplest recursive definition of the cartesian product I can think of looks like this. You can see that like yours, this has a loop -- actually, two loops embedded in a list comprehension. Unlike yours, this can handle two or more sequences:
def product(*seqs):
if not seqs:
return [[]]
else:
return [[x] + p for x in seqs[0] for p in product(*seqs[1:])]
Here's a walk-through to give you a sense of how it works. By definition, the cartesian product of an empty sequence (product()
) is a sequence containing the empty sequence. In other words, product()
== [[]]
-- see here for why.
Now let's say we call product([1, 2, 3])
-- seqs
is non-empty, so the return value is the result of the list comprehension. In this case, product(*seqs[1:])
== product(*[])
== product()
== [[]]
, so the list comprehension is equivalent to this:
[[x] + p for x in seqs[0] for p in [[]] ]
Which is equivalent to all of these:
[[x] + [] for x in seqs[0]]
[[x] for x in seqs[0]]
[[1], [2], [3]]
Adding another sequence, we have product([4, 5, 6], [1, 2, 3])
. Now the list comprehension looks like this:
[[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])]
[[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]]
[[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]]
The pattern continues from there; for each additional sequence, each of the values in the sequence is prepended to each of the values in the cartesian product of the following sequences.
Use itertools
import itertools
print list(itertools.product(input1, input2))
Semantically this is equivalent to:
for i_1 in input_1:
for i_2 in input_2:
for i_3 in input_3:
...
for i_n in input_n:
#do something with i_1, i_2, i_3, ..., i_n
Where n is the number of arguments you pass to product
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With