How can I get all possible permutations of a list with Common Lisp?

Question

I'm trying to write a Common Lisp function that will give me all possible permutations of a list, using each element only once. For example, the list '(1 2 3) will give the output ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)).

I already wrote something that kind of works, but it's clunky, it doesn't always work and I don't even really understand it. I'm not asking for code, just maybe for some guidance on how to think about it. I don't know much about writing algorithms.

Thanks, Jason

Answer 1

I'm not sure if your question is about Common Lisp, or about the algorithm.

There are similar problems (and solutions) for other languages here, e.g., Python. Python can often be translated into Common Lisp virtually line-for-line, so pick one and port it? :-)

Answer 2

As a basic approach, "all permutations" follow this recursive pattern:

  all permutations of a list L is:
    for each element E in L:
      that element prepended to all permutations of [ L with E removed ]

If we take as given that you have no duplicate elements in your list, the following should do:

(defun all-permutations (list)
  (cond ((null list) nil)
        ((null (cdr list)) (list list))
        (t (loop for element in list
             append (mapcar (lambda (l) (cons element l))
                            (all-permutations (remove element list)))))))

Answer 3

Walk through your list, selecting each element in turn. That element will be the first element of your current permutation.

Cons that element to all permutations of the remaining elements.