{VERSION 4 0 "IBM INTEL NT" "4.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 267 "" 0 24 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" 
-1 268 "Helvetica" 1 14 128 0 0 1 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "" -1 
269 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 270 "
Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 272 "Helve
tica" 0 14 128 0 0 1 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "" -1 273 "Helvetica
" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 275 "" 1 14 255 0 
0 1 0 2 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 1 14 0 0 255 1 0 2 1 0 
0 0 0 0 0 1 }{CSTYLE "" -1 277 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 
0 0 0 1 }{CSTYLE "" -1 278 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 279 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
280 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 
{CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 
0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Ti
mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }
{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 
2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 
256 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }1 1 
0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Author" -1 257 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 8 8 1 0 1 0 2 2 
0 1 }{PSTYLE "Normal" -1 264 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 
2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 3 36 1 0 2 2 0 1 }{PSTYLE "Normal" 
-1 265 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 
1 0 0 0 0 3 36 1 0 2 2 0 1 }{PSTYLE "Normal" -1 266 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 3 36 1 0 2 2 
0 1 }{PSTYLE "Normal" -1 267 1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 
2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 3 36 1 0 2 2 0 1 }{PSTYLE "Normal" 
-1 268 1 {CSTYLE "" -1 -1 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 
1 0 0 0 0 3 36 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 267 44 "Cartesian Product of a \+
Finite Number of Sets" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 268 31 "
Mth 355/399 Oct 10 2001 Maple 6" }}{PARA 0 "" 0 "" {TEXT 269 16 "Bent \+
E. Petersen" }}{PARA 0 "" 0 "" {TEXT 270 40 "Filename: 355f2001-cartes
ian-product.mws" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT 279 13 "Supplement to" }}{PARA 264 "" 0 "
" {TEXT 276 41 "Set Theory - Maple Programming Assignment" }}{PARA 
265 "" 0 "" {TEXT 275 43 "Mth 355 Fall 2001 Assignment 2. Due Oct 12.
" }}{PARA 266 "" 0 "" {TEXT 272 30 "Mth 355/399 Oct 5 2001 Maple 6" }}
{PARA 267 "" 0 "" {TEXT 273 16 "Bent E. Petersen" }}{PARA 268 "" 0 "" 
{TEXT 277 44 "Filename: 355f2001-assign-002-maple-prog.mws" }}{PARA 0 
"" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 285 "In assig
nment 2 I gave you a procedure to compute the Cartesian product of two
 sets and asked you to write a procedure to compute the Cartesian prod
uct of any number of sets (problem 3). I did give you a hint how you c
ould handle 3 sets. This problem created quite a bit of difficulty!" }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 182 "In this
 note I will present 2 solutions - a recursive solution and a nonrecur
sive one. I left plenty of room for improvement in case you wanted to \+
try your hand at improving my code." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 0 "" 0 "" {TEXT -1 49 "Here is the original carp() procedure fo
r 2 sets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 15 "carp:=proc(X,Y)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
14 "  local Z,x,y;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "  Z:=\{\};" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "  for x in X do" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 17 "    for y in Y do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 
0 25 "      Z:=Z union \{[x,y]\};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 
"    od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "  od;" }}{PARA 0 "> " 0 
"" {MPLTEXT 1 0 9 "return Z;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
31 "Let's test it on some test sets" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "A1:=\{1,3,5,9\}; A2:=\{12,
13,15\}; A3:=\{2,4,6\}; A4:=\{5,9\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%#A1G<&\"\"\"\"\"$\"\"&\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#
A2G<%\"#7\"#8\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A3G<%\"\"#\"\"
%\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A4G<$\"\"&\"\"*" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "carp(A1,A2);" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#<.7$\"\"\"\"#77$F%\"#87$F%\"#:7$\"\"$F&7$F,F(7$F,F
*7$\"\"&F&7$F0F(7$F0F*7$\"\"*F&7$F4F(7$F4F*" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 79 " According to the hint \+
I gave you we can use carp() to compute a triple product" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 80 "Z:=
\{\}: for x in carp(A1,A2) do for a in A3 do Z:=Z union \{[op(x),a]\};
 od; od; Z;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#<F7%\"\"&\"#8\"\"#7%F%F
&\"\"%7%F%\"#:F'7%F%\"#7F)7%F%F-\"\"'7%F%F&F/7%\"\"\"F-F'7%F2F-F)7%F2F
-F/7%F2F&F'7%F2F&F)7%F2F&F/7%F2F+F'7%F2F+F)7%F2F+F/7%\"\"$F-F'7%F<F-F)
7%F<F-F/7%F<F&F'7%F<F&F)7%F<F&F/7%F<F+F'7%F<F+F)7%F<F+F/7%F%F-F'7%F%F+
F)7%F%F+F/7%\"\"*F-F'7%FIF-F)7%FIF-F/7%FIF&F'7%FIF&F)7%FIF&F/7%FIF+F'7
%FIF+F)7%FIF+F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 
0 "" {TEXT -1 204 "Once we have a triple product we can use the same p
rocess to do a quadruple product. It only remains to do this successiv
e multiplication either by recursion or by a loop over the arguments (
the factors)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 92 "Now lets write a proce
dure  mcarp()  to compute the Cartesian product of any number of sets.
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 278 17 "Recu
rsive mcarp()" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 43 "This recursive follows the hint I gave you." }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "mcar
p:=proc()" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "  local Z,k,x,y;  opti
on remember;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "if nargs=0 then" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "  Z:=\{\};" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 17 "elif nargs=1 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
13 "  Z:=args[1];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "else Z:=\{\};
" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "  for x in mcarp( seq(args[k], \+
k=1..nargs-1) ) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "    for y in \+
args[nargs] do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "      Z:= Z unio
n \{[op(x),y]\};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "    od;" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "  od;" }}{PARA 0 "> " 0 "" {MPLTEXT 
1 0 3 "fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "return Z;" }}{PARA 0 "
> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 134 "The \"option remember\" is not reall
y needed but it speeds up recursive routines by a great deal (in excha
nge for using much more RAM). " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 182 "Note how the routine recurses - to compu
te the product of  n  sets it calls itself to find the product of  n-1
 sets and then uses the hint to take the product with an additional se
t." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "Let
's test or mcarp():" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 13 "mcarp(A1,A2);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#<.7$\"\"\"\"#77$F%\"#87$F%\"#:7$\"\"$F&7$F,F(7$F,F*7$\"
\"&F&7$F0F(7$F0F*7$\"\"*F&7$F4F(7$F4F*" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 16 "mcarp(A1,A2,A3);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#<
F7%\"\"&\"#8\"\"#7%F%F&\"\"%7%F%\"#:F'7%F%\"#7F)7%F%F-\"\"'7%F%F&F/7%
\"\"\"F-F'7%F2F-F)7%F2F-F/7%F2F&F'7%F2F&F)7%F2F&F/7%F2F+F'7%F2F+F)7%F2
F+F/7%\"\"$F-F'7%F<F-F)7%F<F-F/7%F<F&F'7%F<F&F)7%F<F&F/7%F<F+F'7%F<F+F
)7%F<F+F/7%F%F-F'7%F%F+F)7%F%F+F/7%\"\"*F-F'7%FIF-F)7%FIF-F/7%FIF&F'7%
FIF&F)7%FIF&F/7%FIF+F'7%FIF+F)7%FIF+F/" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 19 "mcarp(A1,A2,A3,A4);" }}{PARA 12 "" 1 "" {XPPMATH 20 "
6#<do7&\"\"$\"#:\"\"%\"\"*7&F(F&\"\"'F(7&\"\"\"\"#8F'F(7&F(F&F*\"\"&7&
F%F&F*F(7&F,F-\"\"#F(7&F%F&F*F/7&F,F-F'F/7&F%F&F2F(7&F%F&F'F/7&F,F-F2F
/7&F/F-F2F/7&F/F-F2F(7&F/F-F'F/7&F/F-F'F(7&F/F&F2F/7&F/F&F2F(7&F/\"#7F
'F/7&F/F?F'F(7&F/F?F*F/7&F/F?F*F(7&F/F-F*F/7&F/F-F*F(7&F,F?F2F/7&F,F?F
2F(7&F,F?F'F/7&F,F?F'F(7&F,F?F*F/7&F,F?F*F(7&F,F-F*F/7&F,F-F*F(7&F,F&F
2F/7&F,F&F2F(7&F,F&F'F/7&F,F&F'F(7&F,F&F*F/7&F,F&F*F(7&F%F?F2F/7&F%F?F
2F(7&F%F?F'F/7&F%F?F'F(7&F%F?F*F/7&F%F?F*F(7&F%F-F2F/7&F%F-F2F(7&F%F-F
'F/7&F%F-F'F(7&F%F-F*F/7&F%F-F*F(7&F%F&F2F/7&F/F?F2F/7&F/F?F2F(7&F/F&F
'F/7&F/F&F'F(7&F/F&F*F/7&F/F&F*F(7&F(F?F2F/7&F(F?F2F(7&F(F?F'F/7&F(F?F
'F(7&F(F?F*F/7&F(F?F*F(7&F(F-F2F/7&F(F-F2F(7&F(F-F'F/7&F(F-F'F(7&F(F-F
*F/7&F(F-F*F(7&F(F&F2F/7&F(F&F2F(7&F(F&F'F/7&F(F&F'F(" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 280 20 "Nonrecur
sive mcarp()" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 144 "A nonrecursive  mcarp()  is harder to write, b
ut easier to understand and will probably run more efficiently. Let's \+
call this version  mcarp2()." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "mcarp2:=proc()" }}{PARA 0 ">
 " 0 "" {MPLTEXT 1 0 19 "  local Z,U,k,x,y; " }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 15 "if nargs=0 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "
  Z:=\{\};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "elif nargs=1 then" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "  Z:=args[1];" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 16 "else Z:=args[1];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 
24 "for k from 2 to nargs do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "   U
:=\{\};" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "for x in Z do" }}{PARA 
0 "> " 0 "" {MPLTEXT 1 0 23 "    for y in args[k] do" }}{PARA 0 "> " 
0 "" {MPLTEXT 1 0 30 "      U:= U union \{[op(x),y]\};" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 7 "    od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "  \+
od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "  Z:=U;" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 3 "od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "fi;" }}{PARA 
0 "> " 0 "" {MPLTEXT 1 0 9 "return Z;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 
0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 15 "Let's test it -" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "mcarp2(A1,A2);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#<.7$\"\"\"\"#77$F%\"#87$F%\"#:7$\"\"$F&7$F,F(7$F
,F*7$\"\"&F&7$F0F(7$F0F*7$\"\"*F&7$F4F(7$F4F*" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 17 "mcarp2(A1,A2,A3);" }}{PARA 12 "" 1 "" {XPPMATH 
20 "6#<F7%\"\"&\"#8\"\"#7%F%F&\"\"%7%F%\"#:F'7%F%\"#7F)7%F%F-\"\"'7%F%
F&F/7%\"\"\"F-F'7%F2F-F)7%F2F-F/7%F2F&F'7%F2F&F)7%F2F&F/7%F2F+F'7%F2F+
F)7%F2F+F/7%\"\"$F-F'7%F<F-F)7%F<F-F/7%F<F&F'7%F<F&F)7%F<F&F/7%F<F+F'7
%F<F+F)7%F<F+F/7%F%F-F'7%F%F+F)7%F%F+F/7%\"\"*F-F'7%FIF-F)7%FIF-F/7%FI
F&F'7%FIF&F)7%FIF&F/7%FIF+F'7%FIF+F)7%FIF+F/" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 20 "mcarp2(A1,A2,A3,A4);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#<do7&\"\"$\"#:\"\"%\"\"*7&F(F&\"\"'F(7&\"\"\"\"#8F'F(7&
F(F&F*\"\"&7&F%F&F*F(7&F,F-\"\"#F(7&F%F&F*F/7&F,F-F'F/7&F%F&F2F(7&F%F&
F'F/7&F,F-F2F/7&F/F-F2F/7&F/F-F2F(7&F/F-F'F/7&F/F-F'F(7&F/F&F2F/7&F/F&
F2F(7&F/\"#7F'F/7&F/F?F'F(7&F/F?F*F/7&F/F?F*F(7&F/F-F*F/7&F/F-F*F(7&F,
F?F2F/7&F,F?F2F(7&F,F?F'F/7&F,F?F'F(7&F,F?F*F/7&F,F?F*F(7&F,F-F*F/7&F,
F-F*F(7&F,F&F2F/7&F,F&F2F(7&F,F&F'F/7&F,F&F'F(7&F,F&F*F/7&F,F&F*F(7&F%
F?F2F/7&F%F?F2F(7&F%F?F'F/7&F%F?F'F(7&F%F?F*F/7&F%F?F*F(7&F%F-F2F/7&F%
F-F2F(7&F%F-F'F/7&F%F-F'F(7&F%F-F*F/7&F%F-F*F(7&F%F&F2F/7&F/F?F2F/7&F/
F?F2F(7&F/F&F'F/7&F/F&F'F(7&F/F&F*F/7&F/F&F*F(7&F(F?F2F/7&F(F?F2F(7&F(
F?F'F/7&F(F?F'F(7&F(F?F*F/7&F(F?F*F(7&F(F-F2F/7&F(F-F2F(7&F(F-F'F/7&F(
F-F'F(7&F(F-F*F/7&F(F-F*F(7&F(F&F2F/7&F(F&F2F(7&F(F&F'F/7&F(F&F'F(" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "23" 0 }
{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }