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)))))
For example:
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))))
For example:
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