## 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.

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

```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