Lexicographic Permutations

March 9, 2010

The next-perm function is tricky, which is not a compliment. Xlist holds the list in reverse order, xn, … x1, because that makes it easier to work at the tail end of the list. The next loop finds the element y to replace. The swap function performs the replacement and rearrangement. When the greatest lexicograpic permutation is reached, the call to (reverse zs) goes “around the corner” to the least lexicographic permutation:

(define (next-perm lt? zs)
  (if (null? zs) zs
    (let next ((xlist (list (car zs))) (ys (cdr zs)))
      (cond ((null? ys) (reverse zs))
            ((not (lt? (car ys) (car xlist)))
              (next (cons (car ys) xlist) (cdr ys)))
            (else
              (letrec ((swap
                        (lambda (xs)
                          (cond ((null? (cdr xs))
                                  (cons (car ys) (cons (car xs) (cdr ys))))
                                ((lt? (car ys) (cadr xs))
                                  (cons (car xs) (swap (cdr xs))))
                                (else (append (cons (car ys) (cons (cadr xs) (cddr xs)))
                                              (cons (car xs) (cdr ys))))))))
                (swap xlist)))))))

Perms generates successive permutations, counting the permutations to know when to stop:

(define (perms lt? xs)
  (define (fact n) (if (<= n 1) 1 (* n (fact (- n 1)))))
  (let loop ((n (fact (length xs))) (xs xs) (xss '()))
    (if (zero? n) xss
      (loop (- n 1) (next-perm lt? xs) (cons xs xss)))))

Here are some examples:

> (perms < '())
(())
> (perms < '(1))
((1))
> (perms < '(1 1))
((1) (1))
> (perms < '(4 3 2 1))
((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))

Our code derives from Lawrence Paulson’s Book ML for the Working Programmer. You can run the program at http://programmingpraxis.codepad.org/Y8uDXfrXx.

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 635 other followers

%d bloggers like this: