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

Triplicity

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... – Garrulity

If this is homework, please tag it as such. – Pelecypod

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. – Triplicity

Answer 1

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

Pacien

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.) – Triplicity

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. – Pacien

(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")))) – Brooder

Is the (null list) check needed? The (null (cdr list)) condition should be enough, I think. – Dolorous

Answer 2

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.

Peristyle

could wrap the cond in remove-duplicates if unique permutations required – Jamboree

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.

Blayne

Answer 4

I find the following implementation quite readable. And it implements literally how @CarlSmotricz's answer explains.

(defun all-permutations (items)
  (loop
    for item in items
    for other-items = (remove item items)
    for other-items-permutations = (all-permutations other-items)
    appending
    (if other-items-permutations
        (mapcar #'(lambda (l)
                    (cons item l))
                other-items-permutations)
        (list (list item)))))

Guillemot