4
\$\begingroup\$

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?

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

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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