Generate combinations

Question

I am trying to write a function in Lisp that generates all possible combinations of given keys and values. Here is an example input and output:

Input: '((key1 . (v1 v2))
         (key2 . (v3 v4)))

Output: '(((key1 . v1)(key2 . v3))
          ((key1 . v1)(key2 . v4))
          ((key1 . v2)(key2 . v3))
          ((key1 . v2)(key2 . v4)))

Currently, my function for doing this is the following:

(defun generate-selectors (selectors)
  (cond ((= (length selectors) 0) nil)
        ((= (length selectors) 1)
         (let* ((keys (mapcar #'first selectors))
                (key (first keys))
                (values (rest (assoc key selectors))))
           (loop for val in values
                 collect (cons key val))))
        (t
         (let* ((keys (mapcar #'first selectors))
                (key (first keys))
                (values (rest (assoc key selectors)))
                (rest (remove (assoc key selectors) selectors)))
            (loop for r in (generate-selectors rest)
                  append (loop for val in values
                               collect (cons (cons key val) (list r))))))))

For the input given above, the function works as expected:

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5))))
  (((KEY1 . V1) (KEY2 . V4))
   ((KEY1 . V2) (KEY2 . V4))
   ((KEY1 . V3) (KEY2 . V4))
   ((KEY1 . V1) (KEY2 . V5))
   ((KEY1 . V2) (KEY2 . V5))
   ((KEY1 . V3) (KEY2 . V5)))

However, for longer input, the output is no longer correct!

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5)) (key3 . (v6))))
  (((KEY1 . V1) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V2) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V3) ((KEY2 . V4) (KEY3 . V6)))
   ((KEY1 . V1) ((KEY2 . V5) (KEY3 . V6)))
   ((KEY1 . V2) ((KEY2 . V5) (KEY3 . V6)))
   ((KEY1 . V3) ((KEY2 . V5) (KEY3 . V6))))

Note in the output above that KEY2 and KEY3 are nested in another sublist. The correct output should look like this:

(((KEY1 . V1) (KEY2 . V4) (KEY3 . V6))
 ((KEY1 . V2) (KEY2 . V4) (KEY3 . V6))
 ...                                  )

What is causing this in my generate-selectors function?

EDIT: When not wrapping r in a list, I get the following output:

> (generate-selectors '((key1 . (v1 v2 v3)) (key2 . (v4 v5)) (key3 . (v6))))
  (((KEY1 . V1) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V2) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V3) (KEY2 . V4) KEY3 . V6)
   ((KEY1 . V1) (KEY2 . V5) KEY3 . V6)
   ((KEY1 . V2) (KEY2 . V5) KEY3 . V6)
   ((KEY1 . V3) (KEY2 . V5) KEY3 . V6))

Answer 1

Here:

(cons (cons key val) (list r))

R is obtained recursively and is a list. You are wrapping it inside a list. Try instead:

(cons (cons key val) r)

Also, when you call append in the general case, you expect a list of lists. Your base case is however not producing a list of lists, only a list. You need to put the additional list in the base case around the cons:

(loop for val in values
      collect (list (cons key val)))

Another version

If you don't need keys, this one is a little bit simpler. I (re)named the function product, following Renzo's answer, because what you are doing is called the Cartesian product:

(defun product (lists)
  (if lists
      (destructuring-bind (head . lists) lists
        (loop
          with product = (product lists) 
          for value in head
          append (loop
                   for tuple in product
                   collect (cons value tuple))))
      (list (list))))

(product '((a b) (0 1 2)))
=> ((A 0) (A 1) (A 2) (B 0) (B 1) (B 2))