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

usually it is a good idea to post the code you have written so far. This way we can see which way you are thinking... — Rainer Joswig, Jan 18 '10 at 17:30
This isn't homework. I purposely omitted the code I have so far. I don't want to taint the answers with my flawed idea. — Jason, Jan 19 '10 at 20:41

score 19 · Answer 1 · edited May 10 '22 at 17:13

19

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

edited May 10 '22 at 17:13

BitTickler

10,905
5
32
53

answered Jan 18 '10 at 17:09

Vatine

20,782
4
54
70

Thank you! This is kind of like what I had, but with some small and important differences. The only problem I see with this is that (all-permutations '(1 2 3)) and (all-permutations '(1 1 2 3)) give the same result, but that should be easy enough to change. (My ultimate goal here is to scramble words.) – Jason Jan 19 '10 at 20:51
If you have indistinguishable elements, it gets a little bit trickier, you'll need to do some pre-processing to avoid generating "the same" permutation more than once. However, instead of using a list as above, using a vector of (SYMBOL . COUNT) as the data structure you pass down and decrementing count (on a copy!) instead of deleting should take care of that, too. – Vatine Jan 20 '10 at 06:42
(defun permutations () (labels ((do-permutations (items) (if items (mapcan (lambda (x) (mapcar (lambda (y) (cons x y)) (do-permutations (remove x items)))) items) '(())))) (do-permutations '("Guy" "Man" "Dude")))) – Carlos Konstanski Feb 10 '18 at 13:55
Is the (null list) check needed? The (null (cdr list)) condition should be enough, I think. – Dietrich Jun 24 '19 at 02:06

score 11 · Answer 2 · answered Dec 09 '11 at 16:31

Here is the answer which allows repeated elements. The code is even more "lispish" as it doesn't use loop, with the disadvantage of being less comprehensible than Rainer Joswig's solution:

(defun all-permutations (lst &optional (remain lst))
  (cond ((null remain) nil)
        ((null (rest lst)) (list lst))
        (t (append
            (mapcar (lambda (l) (cons (first lst) l))
                    (all-permutations (rest lst)))
            (all-permutations (append (rest lst) (list (first lst))) (rest remain))))))

The optional remain argument is used for cdring down the list, rotating the list elements before entering the recursion.

could wrap the cond in remove-duplicates if unique permutations required — mcheema, Jan 03 '17 at 18:30

score 3 · Answer 3 · answered Jan 18 '10 at 17:09

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.

answered Jan 18 '10 at 17:09

Carl Smotricz

66,391
18
125
167

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

3 Answers3

Linked