Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Cross product of sets using recursion

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.

like image 294
gizgok Avatar asked Feb 26 '13 21:02

gizgok


2 Answers

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.

like image 133
senderle Avatar answered Nov 13 '22 20:11

senderle


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.

like image 20
Udo Klein Avatar answered Nov 13 '22 18:11

Udo Klein