Lisp:如何从列表中包含的列表中获取所有可能的元素组合？

Question

我需要在Common-Lisp中编写一个函数,该函数获取列表列表并返回一个列表,其中包含子列表中元素的所有可能组合.

因此,例如,在诸如((1 2)(1 2))之类的列表上调用该函数应该返回类似((1 1)(1 2)(2 1)(2 2))的列表.输入列表可以是任意长度,并且子列表不保证具有相同的长度.

我知道如何使用子列表中的成对元素(inputtting((1 2)(1 2))返回((1 1)(2 2)),但这对于弧一致性算法来说还不够好我是试着写,我被卡住了.

谢谢.

Answer 1

wvxvw删除了他们的答案,指向亚历山大的一个函数,但它确实提供了一个非常相似的命名函数,实际上做你想要的.而不是alexandria:map-combinations,你需要alexandria:map-product,例如

(apply #'alexandria:map-product #'list '((1 2) (1 2)))

评估为

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

Answer 2

如果您不想使用库,这里的代码可以执行相同的操作,并且可以使用任意数量的列表:

(defun combinations (&rest lists)
  (if (endp lists)
      (list nil)
      (mapcan (lambda (inner-val)
                (mapcar (lambda (outer-val)
                          (cons outer-val
                                inner-val))
                        (car lists)))
              (apply #'combinations (cdr lists)))))

[2]> (combinations '(1 2))
((1) (2))
[3]> (combinations '(1 2) '(3 4))
((1 3) (2 3) (1 4) (2 4))
[4]> (combinations '(1 2) '(3 4) '(5 6))
((1 3 5) (2 3 5) (1 4 5) (2 4 5) (1 3 6) (2 3 6) (1 4 6) (2 4 6))