recursion - 生成LISP中n个给定变量的所有可能的true或false组合的列表

Question

我想定义一个函数，它接受一个输入“n”（变量的数量）并返回所有可能的真值这里，我表示变量I（1<=I<=n）的真值，+I表示真，-I表示假。
例如：

(generate-values 2)

应返回：

((2 1)(2 -1)(-2 1)(-2 -1))

(generate-values 3)

应返回：

((3 2 1)(3 2 -1)(3 -2 1)(3 -2 -1)(-3 2 1)(-3 2 -1)(-3 -2 1)(-3 -2 -1))

以下是我的错误尝试：

(defun generate-values (n)
  (cond
   ((equal n 0) nil)
   (t (list (cons n (generate-values (- n 1)))
            (cons (- 0 n) (generate-values (- n 1)))))))

我知道为什么这是不正确的，但我无法找到生成 (3 2 1)然后继续 (3 2 -1)的方法我的程序输出：

 ((3 (2 (1) (-1)) (-2 (1) (-1))) (-3 (2 (1) (-1)) (-2 (1) (-1))))

任何关于这个问题的帮助都将不胜感激谢谢！

Answer 1

用最简单的方法来处理这个问题可能是最容易的，然后再弄清楚如何使它更简单或更有效。
如果你是递归地做这件事，考虑基本情况是很重要的这里一个合理的基本情况可能是n=0函数总是应该返回一个列表列表。在n=0的情况下，不存在“变量”，因此结果必须是空列表的列表：（）。
对于n是任何其他值的情况，请考虑函数为n-1返回的值这是n-1“变量”上所有组合的列表你所需要做的就是在每一个前面加上n，在每一个前面加上-n，然后确保你得到了所有这些的列表。
直接编码，我们最终得到这样的结果：

(defun table (n)
  (if (zerop n)
      '(())
      (let* ((table (table (1- n)))
             (plus-pos-n (mapcar (lambda (subtable)
                                   (list* n subtable))
                                 table))
             (plus-neg-n (mapcar (lambda (subtable)
                                   (list* (- n) subtable))
                                 table)))
        (nconc plus-pos-n plus-neg-n))))

CL-USER> (table 3)
((3 2 1) (3 2 -1) (3 -2 1) (3 -2 -1) (-3 2 1) (-3 2 -1) (-3 -2 1) (-3 -2 -1))

现在，让我们看看您当前的实现有什么不同之处，注意它当然不一定是完全相同的算法。

(defun generate-values (n)
  (cond
    ((equal n 0)
     nil)
    (t
     (list (cons n
                   (generate-values (- n 1)))
             (cons (- 0 n)
                   (generate-values (- n 1)))))))

从风格上讲，因为只有两个分支，我更希望在这里继续，但这不是问题在攻击基本情况之前，让我们看看递归情况，当n≠0时首先，调用generate values两次；调用一次并保存结果会更有效如果您使用大值n调用此函数，则这可能会在稍后变得很重要，但这不会使函数不正确但请记住生成值返回的是什么；它返回不同组合的列表这意味着您对（cons n（generate values…）的调用将返回一个列表，其中第一个元素是n，其余元素是n-1的组合例如，你正在做如下事情：

CL-USER> (table 1)
((1) (-1))
CL-USER> (cons 2 (table 1))
(2 (1) (-1))

但那不是你想要的您真的想将n添加到这些列表中：

CL-USER> (mapcar (lambda (x)
                   (cons 2 x))
                 (table 1))
((2 1) (2 -1))

这就是递归情况下的问题。基本情况也有问题在递归情况下，需要将n和-n添加到n-1情况下的每个子列表中那么当n=1时会发生什么呢你想得到（cons 1’）和（cons-1’）。但是由于cons的第二个参数将是（generate values 0）结果中的每个列表，因此您确实需要在（generate values 0）返回的列表中包含一些内容需要什么空名单必须在那里所以基本情况需要返回（，），而不是（）因此，在进行这些更改之后，您的代码将是：

(defun generate-values (n)
  (cond
    ((equal n 0)
     '(()))
    (t
     (list (mapcar (lambda (x)
                     (cons n x))
                   (generate-values (- n 1)))
           (mapcar (lambda (x)
                     (cons (- 0 n) x))
                   (generate-values (- n 1)))))))

CL-USER> (generate-values 3)
(((3 (2 (1)) (2 (-1))) (3 (-2 (1)) (-2 (-1))))
 ((-3 (2 (1)) (2 (-1))) (-3 (-2 (1)) (-2 (-1)))))

离得近了，但还是不太对在递归的情况下还有一个最后生成开头有n的值（它们的列表）和开头有-n的值（它们的列表），然后使用list组合它们返回包含两个值的单个列表相反，您需要一个列表，其中包含每个列表的值您希望将它们与append结合起来（或者，由于所有结构都是新生成的，所以可以使用nconc）：

(defun generate-values (n)
  (cond
    ((equal n 0)
     '(()))
    (t
     (append (mapcar (lambda (x)
                       (cons n x))
                     (generate-values (- n 1)))
             (mapcar (lambda (x)
                       (cons (- 0 n) x))
                     (generate-values (- n 1)))))))

CL-USER> (generate-values 3)
((3 2 1) (3 2 -1) (3 -2 1) (3 -2 -1) (-3 2 1) (-3 2 -1) (-3 -2 1) (-3 -2 -1))

最终的实现并不是我刚开始的那样，但在算法上基本上是一样的这些差异主要体现在风格上，但也存在一些效率问题使用ncoc而不是append可以节省一些内存，并且最好缓存递归调用的结果，而不是重新计算它不影响正确性的文体问题可能是使用if而不是cond，使用list*而不是cons（表示我们使用的是列表，而不是cons单元格的树），并且很好地注意到您不必使用（-0n），-使用单个参数返回参数的否定即，（-n）=-n。