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