Cartesian product using python without itertools

Question

I came across this nice line of python code for cartesian product of n number of lists that I would like to bring back on multiple lines :

def cart_product_1(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in cart_product_1(*seqs[1:])]

This seemed pretty straightforward to me, but obviously I'm missing something here. I'm thinking I need to append a list somewhere but can't quite figure it out.

def cart_product_1(result,*seqs):
    if not seqs:
        return [[]]
    else:
        for x in seqs[0]:                       
            for p in cart_product_1(result,*seqs[1:]):
                 result.append([x]+p)
        return result

This leads to a MemoryError.

Instead of return[[x]+p] try doing prodList.append([x]+p) and return the prodList after the two loops. Don't forget to initialize prodList in the beginning. — Vasilis G.
– Vasilis G., Commented Nov 13, 2017 at 23:38

dantiston · Accepted Answer · 2017-11-13 23:39:32Z

3

+50

The line in your example is a list comprehension. Basically, the one line is constructing a list and calculating its members.

To do the same thing, you have to add an initializer and return:

result = []
for x in seqs[0]:                       
    for p in cart_product_1(*seqs[1:]):
        result.append([x]+p)
return result

answered Nov 13, 2017 at 23:39

dantiston

5,4312 gold badges29 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

user2817017 Over a year ago

I'm getting a MemoryError, maybe it has to do with the rest of my code, I edited my question to add the first half of code

dantiston Over a year ago

Where are you declaring a? OutOfMemory errors are notoriously hard to track down. You’ll probably want to read some other resources before tackling it.

user2817017 Over a year ago

I was declaring it out of the function, then I thought maybe IN the function, but since this is recursion it's going to declare every loop? Where CAN I declare it? Could I maybe pass "a" as a argument in the function? Doesn't seem to be working.

dantiston Over a year ago

As you currently have your code, it shouldn't be doing much of anything. If the original version you posted with the list comprehension works, then the version that I posted (with declaring result inside of the function) should work the exact same way. What you have now shouldn't be causing a memory error because you're actually returning much too early. Though, since you are only using one result variable maybe you are making it huge.

user2817017 Over a year ago

Putting the "result" variable inside the arguments was a mistake, instead I had to declare and and reinitialize it ouside of my if statement, but inside of my function.

|

Collectives™ on Stack Overflow

Cartesian product using python without itertools

1 Answer 1

8 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Related