Permutations in python without libraries

Question

I am trying to produce a function that should takes as input a range, and for that range should be return all the possible permutation of that range without use any library.

for example:

per(range(3))

should return:

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

I have done the following but i get an empty list.

def per(l):
    return [l[i]+p for i in range(len(l))for p in per(l[:i] + l [i+1:])]

Does anyone know why i get the empty list and how to solve it?

Answer 1

The issue is that the end condition for you would be when the length of list l is 0 and that returns an empty list back. Hence when length of list is 1, the inner loop never actually runs and hence this also returns an empty list back , and this keeps on happenning and you always get empty lists.

An fix would be to make the end condition when the length of list is 1, and you should return lists of lists, not simple lists. Example -

def per(l):
    if len(l) == 1:
        return [l]
    return [[l[i]] + p for i in range(len(l))for p in per(l[:i] + l [i+1:])]

Demo -

>>> def per(l):
...     if len(l) == 1:
...         return [l]
...     return [[l[i]] + p for i in range(len(l))for p in per(l[:i] + l [i+1:])]
...
>>>
>>> per([2])
[[2]]
>>> per([0,1,2])
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
>>> per([0,1,2, 3])
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
>>> len(per([0,1,2, 3]))
24