Lisp:如何从列表中包含的列表中获取元素的所有可能组合? [英] Lisp: How to get all possible combinations of the elements from lists contained on a list?

问题描述

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

I need to write a function in Common-Lisp that takes a list of lists and returns a list containing all the possible combinations of the elements from the sublists.

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

So, for example calling the function on a list such as ((1 2) (1 2)) should return a list like ((1 1) (1 2) (2 1) (2 2)). The input list can be of any length and the sublists are not guaranted to have the same length.

我知道如何使用子列表中的成对元素来实现这一点(inputtting((1 2)(1 2))返回((1 1)(2 2))，但这对于弧一致性算法还不够好我正在尝试写书，但被卡住了.

I know how to get this with paired elements from the sublists ( inputtting ((1 2) (1 2)) returns ((1 1) (2 2)), but that's not good enough for the arc-consistency algorithm I'm trying to write, and I'm stuck.

谢谢.

推荐答案

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

If you don't want to use a library, here's code to do the same thing, and works with any number of lists:

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

这篇关于Lisp:如何从列表中包含的列表中获取元素的所有可能组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！