Permutations using recursion
18th July 2016
As you will know if you have read previous articles on this blog, I am interested in algorithms that make a compelling case for programming using recursion.
One that came to my attention recently is the algorithm for generating all the permutations of a set of items. The trick is to assume that we know how to solve the case for n-1 items, and then describe how to get from that to the case for n items.
The function will be called with a list of items; for example:
CL-USER > (permutations '(a b c d))
will give:
((A B C D) (A B D C) (A C B D) (A C D B) (A D B C) (A D C B) (B A C D)
(B A D C) (B C A D) (B C D A) (B D A C) (B D C A) (C A B D) (C A D B)
(C B A D) (C B D A) (C D A B) (C D B A) (D A B C) (D A C B) (D B A C)
(D B C A) (D C A B) (D C B A))
In words, the algorithm is:
For each of the n items in the list:
- Find all the permutations of the remaining n-1 items.
- Append the item onto the front of each of those permutations.
- Return a list of all the resulting permutations.
When there are no items the list of permutations is just '(()).
This algorithm is so intuitive that an experienced Lisp programmer could write the Lisp version almost as fast as they can type it in, and it's likely to work perfectly first time. Although there are several non-recursive algorithms, they are definitely less intuitive [1].
Here's Peter Norvig's version, from his book "Paradigms of Artificial Intelligence Programming"[2]:
(defun permutations (bag)
"Return a list of all the permutations of the input."
;; If the input is nil, there is only one permutation:
;; nil itself
(if (null bag)
'(())
;; Otherwise, take an element, e, out of the bag.
;; Generate all permutations of the remaining elements,
;; And add e to the front of each of these.
;; Do this for all possible e to generate all permutations.
(mapcan #'(lambda (e)
(mapcar #'(lambda (p) (cons e p))
(permutations
(remove e bag :count 1 :test #'eq))))
bag)))
Here's my slight modification of this, using map:
(defun permutations (lst)
(if (null lst) '(())
(let (res)
(map nil
(lambda (x)
(setq res
(append res
(map 'list
(lambda (y) (cons x y))
(permutations (remove x lst))))))
lst)
res)))
Avoiding generating a list of permutations
This function is wasteful if we don't need a list of all the permutions, but just want to call a function with each permutation. How can one convert the above routine into one such as:
(map-permutation function list)
where map-permutation calls function with each permutation of list?
Here's the solution:
(defun map-permutations (fun lst)
(if (null lst) (funcall fun nil)
(map nil
(lambda (x)
(map-permutations
(lambda (l) (funcall fun (cons x l)))
(remove x lst)))
lst)))
It seems almost magical that it works, but indeed it does:
CL-USER 31 > (map-permutations #'print '(a b c d)) (A B C D) (A B D C) (A C B D) (A C D B) (A D B C) (A D C B) (B A C D) (B A D C) (B C A D) (B C D A) (B D A C) (B D C A) (C A B D) (C A D B) (C B A D) (C B D A) (C D A B) (C D B A) (D A B C) (D A C B) (D B A C) (D B C A) (D C A B) (D C B A) NIL
- ^ Algorithms to generate permutations on Wikipedia.
- ^ Norvig, Peter "Paradigms of Artificial Intelligence Programming" Morgan Kaufmann Publishers, Inc, San Francisco, 1992, pp 766-768.
blog comments powered by Disqus