=>

=> > Does anyone have a lisp function that performs the Cartesian product

=> > on a list, i.e.,

=> > (CARTESIAN '((A B) (C D) (E F))) will return

=> > ((A C E) (A C F) (A D E) (A D F) (B C E) (B C F) (B D E) (B D F))

=> > not necessarily in that order.

=>

=> (DEFUN CARTESIAN (L)

=> (COND ((NULL L) NIL)

=> ((NULL (CDR L))

=> (MAPCAR #'LIST (CAR L)))

=> (T (MAPCAN #'(LAMBDA (X) (MAPCAR #'(LAMBDA (Y) (CONS Y X)) (CAR L)))

=> (CARTESIAN (CDR L))))))

=>

=> --Denys

thought it might be worthwhile pointing out a small bug in Denys Duchier's

proposed solution.

Note that according to the definition of Cartesian product of a sequence of

sets,

----- | |

| | X = { f: dom(X) --> | | X | for every i in dom(X), f(i) in X(i) }

| | _

the Cartesian product of the empty sequence is the set consisting of the

empty function. Thus, (CARTESIAN '()) should return (()), not ().

The reason I brought this up is not that I think it's terribly important

that (CARTESIAN '()) ==> (NIL), but because not getting this right wound

up complicating the solution. Denys has the recursion bottom out when

L's cdr is empty, and treats an empty L as a special case; once you fix the

bug, the definition can be simplified to

(DEFUN CARTESIAN (L)

(COND ((NULL L) '(()))

(T (MAPCAN #'(LAMBDA (X) (MAPCAR #'(LAMBDA (Y) (CONS Y X)) (CAR L)))

(CARTESIAN (CDR L))))))

So getting the mathematical "specification" right results in simpler code,

as is often the case.

-- rar