如何使用 Common Lisp 获得列表的所有可能排列？

Question

我正在尝试编写一个 Common Lisp 函数，它将为我提供列表的所有可能排列，每个元素仅使用一次。例如，列表 '(1 2 3) 将给出输出 ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))。

我已经写了一些类似的东西，但它很笨拙，并不总是有效，而且我什至不太理解它。我并不是要求提供代码，只是寻求一些关于如何思考它的指导。我对写算法不太了解。

谢谢， 杰森

Answer 1

作为基本方法，“所有排列”都遵循以下递归模式：

 列表 L 的所有排列是：
    对于 L 中的每个元素 E：
      该元素添加到 [ L with E returned ] 的所有排列之前

如果我们认为列表中没有重复元素，则应执行以下操作：

(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 2

这是允许重复元素的答案。该代码更加“口齿不清”，因为它不使用循环，缺点是比 Rainer Joswig 的解决方案更难理解：

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

可选的remain参数用于向下滚动列表，在进入递归之前旋转列表元素。

Answer 3

浏览列表，依次选择每个元素。该元素将是当前排列的第一个元素。

将该元素构造为其余元素的所有排列。

Answer 4

我发现以下实现非常可读。它确实实现了 @CarlSmotricz 的答案的解释。

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