如何使用Common Lisp获取列表的所有可能组合？

我想写一个Common Lisp函数，它会给我列出所有可能的排列，每个元素只能使用一次。例如，列表'（1 2 3）将给出输出（（1 2 3）（1 3 2）（2 1 3）（2 3 1）（3 1 2）（3 2 1））。如何使用Common Lisp获取列表的所有可能组合？

我已经写了一些这样的作品，但它笨重，它并不总是工作，我甚至都没有真正理解它。我不是在寻求代码，只是想了解如何思考它的一些指导。我对写算法不太了解。

感谢，杰森

来源

2010-01-18 Jason

通常这是一个好主意，发布你写的代码到目前为止。这样，我们可以看到你在想什么... – 2010-01-18 17:30:16

如果这是功课，请标记为这样。 – 2010-01-19 08:12:37

这不是家庭作业。我故意省略了我到目前为止的代码。我不想用我有缺陷的想法来玷污答案。 – Jason 2010-01-19 20:41:04

-2

我不知道，如果你的问题是关于Common Lisp的，或有关的算法。

这里还有其他语言的类似问题（和解决方案），例如Python。通常可以将Python翻译成Common Lisp，然后选择一个并移植它？ :-)

来源

2010-01-18 17:02:46 Ken

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

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

来源

2010-01-18 17:09:00 Vatine

谢谢！这有点像我的，但有一些小而重要的区别。我看到的唯一问题是（全排列'（1 2 3））和（全排列'（1 1 2 3））给出了相同的结果，但这应该很容易改变。（我的最终目标是争夺单词。） – Jason 2010-01-19 20:51:10

如果您有难以区分的元素，它会变得有点棘手，您需要执行一些预处理以避免多次生成“相同”排列。但是，不要像上面那样使用列表，而是使用（SYMBOL。COUNT）向量作为您传递的数据结构，并且减少计数（在副本上！）而不是删除应该照顾到这一点。 – Vatine 2010-01-20 06:42:49

（defun定义排列（）（标签（（DO-排列（项目）（如果项目（mapcan（拉姆达（X）（mapcar（拉姆达（Y）（利弊XY））（DO-排列（删除（））））（do-permutations'（“Guy”“Man”“Dude”）））） – 2018-02-10 13:55:51

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

将该元素赋予其余元素的所有排列。

来源

2010-01-18 17:09:16

下面是允许重复元素的答案。该代码是更“lispish”，因为它不使用循环，具有比赖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))))))

可选留个参数用来cdring在列表中向下，旋转列表元素进入递归之前。

来源

2011-12-09 16:31:34

如果唯一排列可以将cond包装在remove-duplicates中需要 – mcheema 2017-01-03 18:30:10

如何使用Common Lisp获取列表的所有可能组合？

回答

相关问题