Lisp: How to get all possible combinations of the

问题:

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.

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.

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.

Thank you.

回答1:

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

回答2:

wvxvw removed their answer that pointed to a function from Alexandria, but it does provide a very similarly named function that actually does what you want. Instead of alexandria:map-combinations, you need alexandria:map-product, e.g.

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

evaluates to

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