## Lexicographic Permutations

### March 9, 2010

The `next-perm`

function is tricky, which is not a compliment. `Xlist`

holds the list in reverse order, *x*_{n}, … *x*_{1}, 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.

Pages: 1 2

[…] 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):

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.

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.

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.