Cartesian product
Author Message
Cartesian product

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.

Thu, 17 Sep 1992 18:15:00 GMT
Cartesian product

Quote:

> 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

Thu, 17 Sep 1992 02:30:00 GMT
Cartesian product

Date: 12 Apr 89 18:15:17 GMT

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.

Thu, 17 Sep 1992 03:25:00 GMT
Cartesian product

=>

=>   > 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

Thu, 17 Sep 1992 21:10:00 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages