[comp.lang.lisp] Cartesian product

maxc0186@sdsu (04/13/89)

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.

Duchier-Denys@cs.yale.edu (Denys Duchier) (04/13/89)

In article <3677@sdsu.UUCP>, ucselx!maxc0186@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

@DOUGHNUT.CS.ROCHESTER.EDU:miller@CS.ROCHESTER.EDU (04/13/89)

From: Brad Miller <miller@CS.ROCHESTER.EDU>

    Date: 12 Apr 89 18:15:17 GMT
    From: ucselx!maxc0186@sdsu


    Does anyone have a lisp function that performs the Cartesian product
    on a list, i.e.,

Why am I getting the feeling that this list is being used to do homework?
----
Brad Miller		U. Rochester Comp Sci Dept.
miller@cs.rochester.edu {...allegra!rochester!miller}

rar@ZOOKS.ADS.COM (Bob Riemenschneider) (04/19/89)

=>   From: Duchier-Denys@cs.yale.edu (Denys Duchier)
=>
=>   In article <3677@sdsu.UUCP>, ucselx!maxc0186@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 ucselx!maxc0186@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