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.
Programming Praxis 
[…] Praxis – Lexicographic Permutations By Remco Niemeijer In today’s Programming Praxis exercise we have to generate all the lexicographic permutations of a list. […]
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]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).
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 seqAs 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.
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.