how to permute n elements from list recursively in python?

Question

I'm trying to figure out how to create all possible n sized permutations from a list recursively.

For example the result of n=2 and list=[0,1,5] would be:

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

or n=3 and list=[2,3]:

[[2, 2, 2], [3, 2, 2], [2, 3, 2], [3, 3, 2], [2, 2, 3], [3, 2, 3], [2, 3, 3], [3, 3, 3]]

(sort of like cartesian product).

I've managed to come up with this piece of code:

def perm(nlist, m):

    if m > len(nlist):
        return 
    if m == 0 or m == len(nlist):
        return [[]]
    results = []            
    for list_i in nlist:
        temp = list(nlist)          
        temp.remove(list_i)
        results.extend(map(lambda x: [list_i] + x, perm(temp, m-1)))
    return results

but it doesn't give permutations like [0,0] [1,1] [2,2] etc.

Does anybody have a solution for me?

How can I make this without using map() and lambda()?

Hint: Don't use `list` as a name, it is a [built-in function](https://docs.python.org/3/library/functions.html#func-list). — , Apr 30 '15 at 14:52
Have you considered using [itertools.permutations](https://docs.python.org/2/library/itertools.html#itertools.permutations)? — Peter Wood, Apr 30 '15 at 14:53
possible duplicate of [How to generate all permutations of a list in Python](http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python) — Peter Wood, Apr 30 '15 at 14:53
This question is about permutations of combinations_with_replacements. NOT just permutations. — David Greydanus, Apr 30 '15 at 15:02

David Greydanus · Answer 1 · 2015-05-01T14:20:01.500

The result you are looking for is the Cartesian product which is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Or, all permutations of all combinations.

from itertools import combinations_with_replacement as iter_combs
from itertools import permutations

def perms_combs(l, n):
    all_combs = []
    for l in list(iter_combs(l, n)):
          [all_combs.append(perm) for perm in list(permutations(l, n))]
    return list(set(all_combs))

>> print list(product([0, 1, 5], repeat=2))
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)]

>> print list(product([2, 3], repeat=3))
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)]

This process, however, is already covered by an itertools functions: product

from itertools import product

>> print product([0, 1, 5], 2)
    [(0, 0), (0, 0), (0, 1), (1, 0), (0, 5), (5, 0), (1, 1), (1, 1), (1, 5), (5, 1), (5, 5), (5, 5)]

>> print product([2, 3], 3)
    [(3, 3, 3), (2, 2, 2), (2, 3, 2), (3, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (2, 2, 3)]

Shashank · Accepted Answer · 2015-04-30T18:10:39.990

This isn't sort of like cartesian product; it's exactly like cartesian product.

>>> from itertools import product
>>> list(product([0,1,5], repeat=2))
[(0, 0), (0, 1), (0, 5), (1, 0), (1, 1), (1, 5), (5, 0), (5, 1), (5, 5)]
>>> list(product([2,3], repeat=3))
[(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)]

The polyfill for itertools.product is the following:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

But since you can't use itertools, you might as well take the liberty of writing a slightly more efficient solution to your problem. Since we are just computing the product of n identical iterables, let's just call it a cartesian exponent:

def cartesian_exponent(li, e=1):
    pools = [li] * e
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    return result

Or recursively using yet another incomprehensible list comprehension:

def cartesian_exponent(li, e=1):
    if e == 1:
        return [[x] for x in li]
    else:
        return [[x]+y for x in li for y in cartesian_exponent(li, e=e-1)]

Which can be compressed to one line:

def cartesian_exponent(li, e=1):
    return [[x] for x in li] if e == 1 else [[x] + y for x in li for y in cartesian_exponent(li, e=e-1)]

But then you would be sacrificing readability for terseness and that's no bueno. The incomprehensible list comprehension is already opaque enough.

Some tests:

>>> cartesian_exponent([0,1,5], e=2)
[[0, 0], [0, 1], [0, 5], [1, 0], [1, 1], [1, 5], [5, 0], [5, 1], [5, 5]]
>>> cartesian_exponent([2,3], e=3)
[[2, 2, 2], [2, 2, 3], [2, 3, 2], [2, 3, 3], [3, 2, 2], [3, 2, 3], [3, 3, 2], [3, 3, 3]]

i like its simplicity but im looking for a recursive solution. thx — Rtucan, Apr 30 '15 at 16:33
@runtuchman A recursive solution has been added to my answer. — Shashank, Apr 30 '15 at 17:34
@runtuchman List comprehensions are just loops that append values to an initially empty list. So just unravel the loops. — Shashank, Apr 30 '15 at 21:18
i couldn't figure out how to unravel them to a simple loop can you show me how? — Rtucan, May 01 '15 at 09:47

how to permute n elements from list recursively in python?

2 Answers2