=> From: ·············@cs.yale.edu (Denys Duchier)
=>
=> In article <····@sdsu.UUCP>, ···············@sdsu writes:
=> > 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
Now that ···············@sdsu's homework deadline is, presumably, past, I
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