Developing a recursive function in Python

Question

I know I can do this with itertools, but I'm actually trying to learn how to start working with recursions.

I want to take the two values in this list...

[0, 1]

...and create a list of lists that contain it's permutations:

[ [0, 0], [0, 1], [1, 0], [1, 1] ]

I can do it with a comprehension and loops:

[ [i, j] for i in range(0, 2) for j in range(0, 2) ]

But that doesn't really scale well.

So if someone could help me understand how to do this with a recursive function that would scale to an arbitrary number of values in the original list I would appreciate it.

If you're interested, you can see the code for itertools.product here: docs.python.org/2/library/itertools.html#itertools.product — TerryA
– TerryA, Commented Jul 24, 2013 at 12:18
@AntonisChristofides: if the original list contains significantly more than two elements, the 'for' loops will eventually become unmanageable. — rwjones
– rwjones, Commented Jul 24, 2013 at 12:32
Those are not permutations. Permutations of this list would be [0,1] and [1,0]. You mean sth like combinations of n elements, taken from a base set. — Johannes Charra
– Johannes Charra, Commented Jul 24, 2013 at 12:37

chepner · Accepted Answer · 2013-07-24 13:54:51Z

4

def cartesian_product(base, n=0):
        if (n ==  len(base)-1):
                return [[i] for i in base]
        res = []
        for i in base:
                for element in cartesian_product(base, n+1):
                        res.append([i]+element)
        return res

*Input: * cartesian_product([1,2])

*Output: * [[1, 1], [1, 2], [2, 1], [2, 2]]

Not the best way to do, but it's recursive. Each element is composed of one of the base element (1 or 2 in the exemple) + one element of the previous size (so [1] or [2]).

edited Jul 24, 2013 at 13:54

chepner

538k77 gold badges594 silver badges746 bronze badges

answered Jul 24, 2013 at 12:42

elnabo

2641 gold badge2 silver badges10 bronze badges

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

Collectives™ on Stack Overflow

Developing a recursive function in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related