Showing all possible permutations from a set

Question

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?

• 200_success: If m == len(nlist) then shouldn't it return [nlist] instead of [[]]?
• fishiwhj: @200_success Return [nlist] does not work in this recursive structure, which is to select the first element of a list recursively until empty.
• 200_success: 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.)
• Roman Susi: @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
• fishiwhj: @RomanSusi Thanks! Maybe I can read the source code of the permutation function in Python standard library.

Answer 1

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