Permutations using recursion 2
20th July 2016
In the previous article Permutations using recursion I wrote about an intuitive recursive algorithm to find all the permutations of n items.
Here's an alternative recursive algorithm that's perhaps even more intuitive:
- Find all the permutations of n-1 of the items.
- Insert the remaining item into the n possible positions in each of those permutations.
- Return a list of all the resulting permutations.
Again, when there are no items the list of permutations is just '(()).
First we need a function insert that inserts an item before the nth element of a list:
(defun insert (n x lis) (if (zerop n) (cons x lis) (cons (car lis) (insert (1- n) x (cdr lis)))))
CL-USER > (insert 3 'e '(a b c d)) (A B C E D)
Next, the function all generates a list of all the lists generated by inserting an item into a list:
(defun all (x lis) (let (res) (dotimes (n (1+ (length lis)) res) (push (insert n x lis) res))))
CL-USER > (all 'e '(a b c d)) ((A B C D E) (A B C E D) (A B E C D) (A E B C D) (E A B C D))
Finally, here's the full definition of permutations2:
(defun permutations2 (lis) (cond ((null lis) '(())) (t (mapcan (lambda (l) (all (car lis) l)) (permutations2 (cdr lis))))))
Trying it out:
CL-USER > (permutations2 '(a b c d)) ((D C B A) (D C A B) (D A C B) (A D C B) (D B C A) (D B A C) (D A B C)
(A D B C) (B D C A) (B D A C) (B A D C) (A B D C) (C D B A) (C D A B)
(C A D B) (A C D B) (C B D A) (C B A D) (C A B D) (A C B D) (B C D A)
(B C A D) (B A C D) (A B C D))
This routine is about a factor 0f 20 faster than the routine permutations in my previous article.
Here's a slight modification using map rather than mapcan:
(defun permutations3 (lis) (cond ((null lis) '(())) (t (let (res) (map nil (lambda (l) (map nil (lambda (x) (push x res)) (all (car lis) l))) (permutations3 (cdr lis))) res))))
blog comments powered by Disqus