lisp - 递归 - 在列表中获取所有可能的对

Question

这是一个家庭作业，我不允许使用循环或全局变量。

基本上功能看起来像

(defun pairs (1 4)

并像这样制作一个列表(1 2 3 4)并找到所有可能的对，所以它应该返回((1 2) (1 3) (1 4) (2 3) (2 4) (3 4)). 我尝试过的所有代码都没有给我所有的配对，通常会导致从头到尾只得到配对，比如(1 2) (2 3) (3 4). 我也不确定基本情况是否应该是 when(= m n)或(= (1- m) n).

Answer 1

您不太可能mapcon在您的解决方案中使用，所以我不觉得下面的代码会给您一个家庭作业的答案。但是，如果您阅读了内容mapcon并了解如何实现它，则可以使用以下内容作为解决方案的指南。

(defun pairs (list)
  (mapcon (lambda (tail)
            (mapcar (lambda (y)
                      (list (first tail) y))
                    (rest tail)))
          list))

CL-USER> (pairs '(1 2 3 4))
;=> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

这里的想法是，如果您想在原始列表的尾部递归。也就是说，考虑(1 2 3 4)并从中生成一些对，然后考虑(2 3 4)并从中生成一些对，然后(3 4)，然后从中(4)生成（一个空集）一些对：

(1 2 3 4) → [1, (2 3 4)] ↦ ((1 2) (1 3) (1 4))
  (2 3 4) → [2,   (3 4)] ↦ ((2 3) (2 4))
    (3 4) → [3,     (4)] ↦ ((3 4))
      (4) → [4,      ()] ↦ ()

然后只需将 ((1 2) (1 3) (1 4)), ((2 3) (2 4)), ((3 4)) 和 () 放在一起就可以得到 ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))。