如何使用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

作为一种基本方法,"所有排列"遵循这种递归模式:

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

如果我们认为您的列表中没有重复元素,则应执行以下操作:

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

可选的retain参数用于cdring down list,在进入递归之前旋转列表元素.