recursion - Lisp 排列函数——我在这里做错了什么？

Question

我正在尝试学习一些 Common Lisp。我已经习惯了大括号命令式语言，但仍然难以理解 Lisp 风格的思维和语法。

下面是我正在尝试编写的排列函数。目前已损坏。

如果我运行这个函数

(permutations '(1 2 3))

我可以在标记为“and here”的断点处看到在该点生成诸如 (2 3)、(3 2)、(1 3) 等列表。但是随后通过在 SLIME 中运行跟踪，我看到置换函数在该调用之后返回 (2)、(3) 和 (1)(lisp 中的第一项)。然后顶层函数只返回 nil(我也不明白)。

(defun permutations (coll)
(if (= 1 (length coll))
 (print (list (first coll)))
  (loop for el in coll do
   (map 'list #'(lambda (combos) 
          (if 
               (break "you got here with arguments ~:S." (listp combos))
               (cons el combos)
               (break "and here: ~:S " (list el combos))))

    (permutations (remove el coll))
    ))))

我在这里做错了什么？在此先感谢您的帮助。

编辑:这是我根据 jlahd 的评论更改功能后的结果。这返回(((1 ((2 3))) (1 ((3 2)))) ((2 ((1 3))) (2 ((3 1)))) ((3 ((1 2)) ) (3 ((2 1))))) 在使用原始示例调用时。还没有想出如何修复嵌套列表的问题。

(defun permutations (coll)
  (if (= 1 (length coll))
      (print (list (first coll)))
      (loop for el in coll collect
           (map 'list #'(lambda (combos) 
                          (list el combos))    
                (permutations (remove el coll))
                ))))

编辑:好的，这里感谢大家的帮助!这是我在 Rörd 和 wxvxw 的评论之后得到的。这将运行并返回 ((1 2 . 3) (1 3 . 2) (2 1 . 3) (2 3 . 1) (3 1 . 2) (3 2 . 1))。与普通列表相比，我不太确定此处的“点对”表示法是什么意思，但除此之外这似乎不错。

(defun permutations (coll)
  (if (not (cdr coll))
      (list (first coll))
      (loop for el in coll nconc
           (mapcar #'(lambda (combos) 
                       (cons el combos))    
                   (permutations (remove el coll))
                   ))))

Answer 1

您将丢弃在循环 中收集的所有数据。将 do 更改为 collect，您会走得更远。