listalgorithmlispcombinationscommon-lisp

Lisp: How to get all possible combinations of the elements from lists contained in a list?


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 guaranteed to have the same length.

I know how to get this with paired elements from the sublists ( inputting ((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.


Solution

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