生成组合

Question

我试图用Lisp编写一个函数，生成给定键和值的所有可能组合。下面是一个输入和输出示例：

Input: '((key1 . (v1 v2))
         (key2 . (v3 v4)))

Output: '(((key1 . v1)(key2 . v3))
          ((key1 . v1)(key2 . v4))
          ((key1 . v2)(key2 . v3))
          ((key1 . v2)(key2 . v4)))

目前，我的职能如下：

(defun generate-selectors (selectors)
  (cond ((= (length selectors) 0) nil)
        ((= (length selectors) 1)
         (let* ((keys (mapcar #'first selectors))
                (key (first keys))
                (values (rest (assoc key selectors))))
           (loop for val in values
                 collect (cons key val))))
        (t
         (let* ((keys (mapcar #'first selectors))
                (key (first keys))
                (values (rest (assoc key selectors)))
                (rest (remove (assoc key selectors) selectors)))
            (loop for r in (generate-selectors rest)
                  append (loop for val in values
                               collect (cons (cons key val) (list r))))))))

对于上述输入，该函数按预期工作：

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5))))
  (((KEY1 . V1) (KEY2 . V4))
   ((KEY1 . V2) (KEY2 . V4))
   ((KEY1 . V3) (KEY2 . V4))
   ((KEY1 . V1) (KEY2 . V5))
   ((KEY1 . V2) (KEY2 . V5))
   ((KEY1 . V3) (KEY2 . V5)))

但是，对于较长的输入，输出不再正确！

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5)) (key3 . (v6))))
  (((KEY1 . V1) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V2) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V3) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V1) ((KEY2 . V5) (KEY3 . V6)))
   ((KEY1 . V2) ((KEY2 . V5) (KEY3 . V6)))
   ((KEY1 . V3) ((KEY2 . V5) (KEY3 . V6))))

注意，在上面的输出中，KEY2和KEY3嵌套在另一个子列表中。正确的输出应该如下所示：

(((KEY1 . V1) (KEY2 . V4) (KEY3 . V6))
 ((KEY1 . V2) (KEY2 . V4) (KEY3 . V6))
 ...                                  )

是什么导致了我的generate-selectors函数出现这种情况？

编辑：当没有将r包装在列表中时，我得到以下输出：

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5)) (key3 . (v6))))
  (((KEY1 . V1) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V2) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V3) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V1) (KEY2 . V5) KEY3 . V6)
   ((KEY1 . V2) (KEY2 . V5) KEY3 . V6)
   ((KEY1 . V3) (KEY2 . V5) KEY3 . V6))

Answer 1

在此：

(cons (cons key val) (list r))

R是递归得到的，是一个列表。你把它包装在一个列表里。试一试：

(cons (cons key val) r)

此外，在一般情况下调用append时，需要一个列表列表。但是，基本大小写不是生成列表列表，而是只生成列表。您需要将附加的list放在cons周围的基本情况中。

(loop for val in values
      collect (list (cons key val)))

另一个版本

如果你不需要钥匙，这个就简单一点。我(重新)将函数命名为product，按照Renzo的回答，因为您所做的称为https://en.wikipedia.org/wiki/Cartesian_product

(defun product (lists)
  (if lists
      (destructuring-bind (head . lists) lists
        (loop
          with product = (product lists) 
          for value in head
          append (loop
                   for tuple in product
                   collect (cons value tuple))))
      (list (list))))

(product '((a b) (0 1 2)))
=> ((A 0) (A 1) (A 2) (B 0) (B 1) (B 2))

Answer 2

鉴于以前的解决办法是正确的，我想提出另一种解决办法。给出了一个列表A1，A2，.下面的函数执行它们的笛卡尔积(A1 x A2 x.(X An)：

(defun cartesian-product (l)
  (if (null l)
      (list nil)
      (loop for x in (car l) 
            nconc (loop for y in (cartesian-product (cdr l)) collect (cons x y)))))

然后，函数generate-selectors可以定义为：

(defun generate-selectors (selectors)
  (cartesian-product (loop for s in selectors
                       collect (loop for val in (cdr s) collect (cons (car s) val)))))