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

Question

我需要用 Common-Lisp 编写一个函数，它接受一个列表列表并返回一个包含子列表中元素的所有可能组合的列表。

因此，例如调用列表上的函数((1 2)(1 2))应该返回一个列表((1 1)(1 2)(2 1)(2 2))。输入列表可以是任意长度，但不保证子列表具有相同的长度。

我知道如何使用子列表中的成对元素获取此信息(输入 ((1 2) (1 2)) 返回 ((1 1) (2 2))，但这对于弧一致性算法来说还不够好我正在尝试写作，但遇到困难。

谢谢。

Answer 1

如果您不想使用库，这里的代码可以做同样的事情，并且可以处理任意数量的列表:

(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))