Permutations using recursion 3
19th April 2017
Previously I've written about recursive procedures for finding a list of permutations. However, if you just want to find the next permutation of a given permutation, I've found a very simple recursive procedure that's also fairly intuitive.
For example:
(next '(2 1 3 4 5))
will give:
(2 1 3 5 4)
The permutations are generated in lexical order; in other words, the order they would be listed in a telephone directory, so if we are generating the permutations of the first five digits, the first permutation will be (1 2 3 4 5) and the last one will be (5 4 3 2 1). Calling:
(next '(5 4 3 2 1))
will return nil to indicate that there are no more permutations.
The recursive algorithm works as follows:
- We divide the current permutation into the head element, and the remaining elements.
For example, for (2 1 3 4 5) we get 2 and (1 3 4 5).
- Unless the remaining elements are in descending order, the next permutation is the head element followed by the next permutation of the remaining elements.
So, in this case, the next permutation is 2 followed by the next permutation of (1 3 4 5).
- If the remaining elements are in descending order, we need to change the head element to give the next permutation, and follow it with the first permutation of the remaining elements.
For example, for (2 5 4 3 1) calling next on (5 4 3 1) will return nil, because there's no next permutation. We therefore need to swap the head element, 2, with the next available digit, and follow it by the first permutation of the remaining digits.
To get the first permutation of the remaining elements we need to arrange them in ascending order. However, we don't need to sort them, because we know they were originally in descending order, so we just need to reverse them: in this example (1 3 4 5).
Now we find the first digit in this list that's greater than the head element. In this case it's 3.
Finally we swap this with the head element to give (3 1 2 4 5) as the next permutation.
The program
To check whether the elements in the list list are descending order we can use:
(apply #'> list)
To find the first item in a list list that's greater than item we use:
(find item list :test #'<)
For example:
> (find 3 '(1 2 4 5 6)) 4
Finally, we use substitute to swap the items old and new in list:
(substitute new old list)
For example:
> (substitute 2 3 '(1 3 4 5)) (1 2 4 5)
Finally, here's the definition of next, following the recursive definition given above:
(defun next (lst) (cond ((not (apply #'> (cdr lst))) (cons (car lst) (next (cdr lst)))) ((> (car lst) (cadr lst)) nil) (t (let* ((rst (reverse (cdr lst))) (old (find (car lst) rst :test #'<))) (cons old (substitute (car lst) old rst))))))
To test it, here's a routine all that repeatedly applies a function to the next permutation of a list until it returns nil:
(defun all (function lst) (when lst (funcall function lst) (all function (next lst))))
For example:
> (all print '(1 2 3)) (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1) nil
blog comments powered by Disqus