About me

About me


RSS feed

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)
   ((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)
   ((null lis) '(()))
   (t (let (res)
        (map nil
         (lambda (l) 
           (map nil 
            (lambda (x) (push x res))
            (all (car lis) l)))
         (permutations3 (cdr lis)))

blog comments powered by Disqus