我正在尝试用 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))
最佳答案
鉴于前面的解决方案是正确的,我想提出一个替代方案。给定列表列表 A1、A2、... An,以下函数执行它们的笛卡尔积 (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)))))
关于list - 生成组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48489812/