Cross product of sets using recursion

Question

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.

I think your final `combine` call needs a `return` in front of it. — DSM, Feb 26 '13 at 21:37
Would you please explain why you want a recursive solution? This is still unclear. — Udo Klein, Feb 27 '13 at 05:53

score 9 · Answer 1 · answered Feb 27 '13 at 00:34

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.

Thanks for this. I used your implementation [over here](http://stackoverflow.com/a/29654551/1774667) to do a compile time cross product in C++ for my amusement. — Yakk - Adam Nevraumont, Apr 15 '15 at 17:47

score 2 · Answer 2 · edited Feb 26 '13 at 21:58

2

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.

edited Feb 26 '13 at 21:58

Joel Cornett

24,192
9
66
88

answered Feb 26 '13 at 21:35

Udo Klein

6,784
1
36
61

2

This completely misses the point of the OP, which is how to improve the recursion. – tacaswell Feb 26 '13 at 22:14
1

@tcaswell: to be fair, the original version said "I'm looking at different ways of solving the problem" and didn't contain the last paragraph, so this made sense at the time. – DSM Feb 26 '13 at 22:22

Cross product of sets using recursion

2 Answers2

Linked

Related