0

I want to make nested list with n elements that includes all permutations of the given list.

Expected output is like:

n=3
print perm(n, [1,2])

[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]

How could I go about writing a python code to do the same.

3
  • 1
    What have you tried so far? Providing the code is not what Stack is for, does your current function not work, or is it written in another language that we can help translate to python?
    – Nate
    Commented May 1, 2015 at 13:47
  • 1
    Take a look at itertools product in the Python docs.
    – PM 2Ring
    Commented May 1, 2015 at 13:49
  • These are not permutations. This is a Cartesian product.
    – Nayuki
    Commented May 1, 2015 at 18:35

3 Answers 3

7

You can solve your problem recursively like this:

def perm(n, a):
  # recursion anchor
  if n <= 0:
    return [[]]
  else:
    result = []
    for smallPerm in perm(n-1, a):
      # take all elements from a
      for elem in a:
        # and prepend them to all permutations we get from perm(n-1, 1)
        result.append([elem] + smallPerm)
    return result

You can write the function as a two-liner but I decided to make it a bit more verbose to make it easier to understand.

Not sure how much you know about recursion, but I do know that it is not easy to understand for beginners... let me try to explain it.

In every recursive function you need a recursion anchor. This is the point where the function does not recurse but directly deliver a result. It usually is a basic/atomic case that is well defined. In this example it is the case where n==0. Since there exists only one permutation with 0 elements which is the empty list, you return a list containing the empty list.

I put n<=0 there so we don't get into troubles if some smartcookie calls perm with e.g. n=-1, but an exception in case of n<0 would also do the job.

Now you build upon this anchor and say, okay my function gives the right result for n==0 so I can trust it when my current n is 1 and I call it with n-1. The trick now is to trust that it gives you the right result for every n-1 no matter where you start! You might wonder how this is possible. That is the thing with recursive functions, while you write them, you already rely on them doing the right job.

Now this means that calling perm(n-1, a) gives you all the permutations with length n-1. Then all what's left to do is to append (or prepend) those permutations with all the elements from a and you have a list with permutations of the size n! Job done.

Note however that it sometimes is necessary to have multiple anchors or an anchor that deals with more than one input possibility.
For example the famous inefficient fibonacci function:

def fib(n):
  # first anchor
  if n == 0:
    return 0
  # second anchor
  if n == 1:
    return 1

  # recursive calls
  if n < 0:
    # negative if even, positive otherwise
    return -fib(-n) if -n % 2 == 0 else fib(-n)
  return fib(n - 2) + fib(n - 1)

Needs two anchors because with fib(n - 2) you go two steps back!

Followup:

Why is this function inefficient? The reason is similar to what Stefan pointed out in the comments about my first solution.
I've made the mistake to put the recursive call within a loop. This does not have to be wrong, but in this case the arguments for the call were not changed by the outer loop which makes it unnecessary. It therefore kept producing the same list every time anew instead of producing it once and then keeping it. The worst about it is that all recursion instances did the same!
You can see how bad that is by looking at the branching factor. The fib function here calls itself twice which means it has a branching factor of two. Therefore if your solution needs to go n steps deep you will have 2^n evaluations of that function.
While this branching factor is constant, my first implementation called itself for every element in a so the branching factor was equal to the number of elements in the list.
I'm glad Stefan did not try out perm(20,[1,2,3]) this would have been 3^20 evaluations which is roughly 3 thousand times more than the 2^20 evaluations for what he tried. Yes, a 3 thousandfold increase only because of one more element. This is exponential runtime in action!
For sake of simplicity I ignore the fact that the problem itself already scales with len(a)**n.

5
  • you are the best! thank you for the very detailed answer. really help me to understnad. Commented May 1, 2015 at 17:36
  • can you please add the two-liner answer so i could compare and learn how to use it? Commented May 1, 2015 at 17:44
  • 1
    @SharonTarrab I added one to my answer. It's also more efficient because I use the proper order of the two loops and thus have a linear rather than exponential number of recursive calls. Commented May 1, 2015 at 18:00
  • thank you Stefan! i will look it up :) Commented May 1, 2015 at 18:04
  • @swenzel Better swap the order of the loops to avoid the exponential number of recursive calls. Of course we have exponential runtime anyway because the result is exponential size, but it's still slower and bad in general. I just tested perm(20, [1, 2]), which took 45.8 seconds. After swapping the loops, it took 6.7 seconds. Discussing this issue might even be a good addition to your otherwise excellent answer. Commented May 1, 2015 at 18:22
2

The itertools library is a very efficient and east to use library provided along with Python, As per your requirements, you can use product method of this module to get the expected output, But there are some other options like permutations, combinations, etc. which you must try as well.

import itertools
n=3

def perm(n, lst):
    return list(itertools.product(lst, repeat=n))

print perm(n, [1,2])
1
  • Just do list(itertools.product(lst, repeat=n)), no need for a comprehension that doesn't do anything. Commented May 1, 2015 at 17:33
2

I realize you asked for a recursive solution, but is that really necessary?

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

Or if you really do need lists inside:

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

And just in case you don't really need the whole thing as a list but just wants to process the triples, product alone does the job:

>>> from itertools import product
>>> for triple in product([1, 2], repeat=3):
        print(triple)

(1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 2, 2)
(2, 1, 1)
(2, 1, 2)
(2, 2, 1)
(2, 2, 2)

Recursive solution:

def perm(elements, n):
    return [[e] + p for p in perm(elements, n-1) for e in elements] if n else [[]]

print(perm([1, 2], 3))

Not the answer you're looking for? Browse other questions tagged or ask your own question.