Lexicographic Permutations

March 9, 2010

Edsger Dijkstra, in his book A Discipline of Programming, describes a function that, given a list of elements and a function that returns a total ordering of those elements, produces the next lexicographic permutation of the list; for instance, the permutations of the list (1 2 3 4) in lexicographic order are (1 2 3 4) (2 1 3 4) (1 3 2 4) (3 1 2 4) (2 3 1 4) (3 2 1 4) (1 2 4 3) (2 1 4 3) (1 4 2 3) (4 1 2 3) (2 4 1 3) (4 2 1 3) (1 3 4 2) (3 1 4 2) (1 4 3 2) (4 1 3 2) (3 4 1 2) (4 3 1 2) (2 3 4 1) (3 2 4 1) (2 4 3 1) (4 2 3 1) (3 4 2 1) (4 3 2 1). With the least significant item in the list at the head, the next greater element than (1 2 3 4) is (2 1 3 4), since the most significant tail of the list doesn’t change, and the next greater permutation differs in the least significant elements. To make a greater permutation, some element of the list must be replaced by a larger element to its left; to make the next permutation, the replacement must happen as far to the left as possible, in the least significant position, and the replacing element must be as small as possible.

Your task is to write functions that return the next lexicographic permutation and a list of all permutations of a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

6 Responses to “Lexicographic Permutations”

  1. [...] Praxis – Lexicographic Permutations By Remco Niemeijer In today’s Programming Praxis exercise we have to generate all the lexicographic permutations of a list. [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/09/programming-praxis-lexicographic-permutations/ for a version with comments):

    import Data.List
    import qualified Data.List.Key as K
    
    perms :: (a -> a -> Bool) -> [a] -> [[a]]
    perms cmp xs = map fst . K.sort (reverse . snd) . map unzip $
                   permutations [(x, length $ filter (cmp x) xs) | x <- xs]
    
  3. Jeff said

    Interesting. My implementation (http://blog.jeffbergman.com/2010/03/09/permutation-generation-in-f-sharp/) was solving a slightly different problem in that I am printing all permutations of all combinations of elements in the list in lexicographic order. For instance, for the list (1,2,3) I print all permutations of the lists (1), (1,2), (1,3), (2,3), and (1,2,3).

  4. Mike said

    In lexicogrphic order, isn’t (1,2,3,4) followed by (1,2,4,3)?

    Anyway, my python version of a generator that returns successive permutations in order.

    def permutations_of( seq ):
        yield seq
        seqlen = len(seq)
        while True:
            j = seqlen - 2
            while j >= 0 and seq[j] >= seq[j+1]:
                j -= 1
    
            if j < 0: break
            
            i= seqlen - 1
            while i > j and seq[i] < seq[j]:
                i -= 1
                    
            seq[j],seq[i] = seq[i],seq[j]
            seq[j+1:] = seq[-1:j:-1]
            yield seq
    
  5. programmingpraxis said

    As explained in the next sentence, the lexicographic order runs from right-to-left, rather than left-to-right, because it is easier when using lists to work at the head of the list, which must be the end (tail) of the permutation.

  6. Valentin said

    Here is mine: http://codepad.org/QEWvFfu5

    Far from the beauty of Knuth version implemented here by Mike but it was my first time to attempt to resolve such problem.

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

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: