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