# Showing all possible permutations from a set

I wrote a small program which shows all possible permutations of choosing m integers from the set ${1, 2, ..., n}$, as follows:

def perm(nlist, m):
"""
Find all possible permutations of choosing m integers from a len(n)-list.

INPUT:
@para nlist: a list of length n.
@para m: a integer.

OUTPUT:
All permutations arranged in ascending order lexicographically.
"""
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


However, this code is inefficient. Perhaps the recursive structure is not well-designed. How can I improve this code?

• If m == len(nlist) then shouldn't it return [nlist] instead of [[]]? Sep 23, 2013 at 2:40
• @200_success Return [nlist] does not work in this recursive structure, which is to select the first element of a list recursively until empty. Sep 23, 2013 at 3:15
• m == len(nlist) is simply not a base case; it should flow through for normal handling. (It should return neither [[]] nor [nlist] — both are wrong.) Sep 23, 2013 at 3:52
• @fishiwhj Python standard library has a function for permutations. It's worth using instead of homebrew one unless you are studying programming/algorithms: docs.python.org/2/library/itertools.html Sep 23, 2013 at 9:13
• @RomanSusi Thanks! Maybe I can read the source code of the permutation function in Python standard library. Sep 23, 2013 at 9:23

As noted by 200_success in the comments, the m == len(nlist) check is a bug that can be fixed by simply removing the condition.

Also, if m > len(nlist): return is almost redundant because you would get an empty list as the result anyway in that case. (The deepest levels of recursion give empty results when the list runs out and the emptiness propagates all the way up)

Turning the function into a generator simplifies it and speeds it up at the same time: from 10.9 ms to 6.6 ms for the case perm(range(6), 6). (Of course I wrapped that in list() when timing the generator version)

def perm(nlist, m):
if m == 0:
yield []
return

for list_i in nlist:
temp = list(nlist)
temp.remove(list_i)
for p in perm(temp, m-1):
yield [list_i] + p