I Might Be Wrong

Computing permutations with a recursive generator expression

Posted in Python by Leif Ryge on October 21, 2008
#!/usr/bin/python2.5
def permute(li):
    """Generate all permutations of a sequence
    >>> for i in permute([1,2,3]): print i
    (1, 2, 3)
    (1, 3, 2)
    (2, 1, 3)
    (2, 3, 1)
    (3, 1, 2)
    (3, 2, 1)"""
    return ((i,)+j for i in li for j in (permute([k for k in li if k is not i])
                                         if len(li) > 1 else [()] ) )

import doctest
doctest.testmod(verbose=True)

7 Responses

Subscribe to comments with RSS.

  1. Auron on RefactorMyCode.com said, on October 22, 2008 at 1:20 am

    Computing permutations with a recursive generator expression…

    Your code works great but addresses a different problem than this one (http://refactormycode.com/codes/523-permutation-of-values), which is really not a permutation (it was my fault).

    I like your one-line solution, although I find it difficult to unde…

  2. Computing permutations with a recursive generator expression…

    First off let me say your solution is already an elegant one. I made a couple changes. First off you’ll notice I turn the list into a Set which removes any duplicate values (that may or may not be what you want). Secondly, I shortened your list compre…

  3. Leif Ryge on RefactorMyCode.com said, on October 30, 2008 at 1:23 pm

    Computing permutations with a recursive generator expression…

    Thanks! I was actually unaware that booleans could be used as getitem keys, which is a very useful trick. I wonder why I’ve seen the horribly ugly idiom_A [below] in wide use instead of the much more elegant B….

  4. Leif Ryge on RefactorMyCode.com said, on October 30, 2008 at 11:56 pm

    Computing permutations with a recursive generator expression…

    Answering my own question: the caveat to idiom_B is that it isn’t short-circuiting. So, if instead of z and y we had z() and y() then evaluating the expression causes BOTH functions to be called (regardless of the value of x) in idiom_B, while in A an…

  5. William Bowers on RefactorMyCode.com said, on October 31, 2008 at 1:41 pm

    Computing permutations with a recursive generator expression…

    That’s very true. In this case it would be better to go with A, as you probably don’t want that last call to permute() to go off. I prefer B in case where it doesn’t really matter, like when Z and Y are both strings or numbers, or when both Z and Y …

  6. 腕時計 高級 said, on September 11, 2013 at 7:00 pm

    kitson 時計

  7. k53 learners said, on February 17, 2014 at 6:13 pm

    Hello excellent blog! Does running a blog like this take
    a massive amount work? I have very little knowledge of programming however I had been
    hoping to start my own blog soon. Anyhow, should you have any suggestions or tips for new
    blog owners please share. I understand this is off subject but I simply wanted to ask.
    Appreciate it!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: