## Version 10 of Cartesian product of a list of lists

Updated 2004-07-29 06:55:56 by eb

Rolf Ade posted a question to the chat asking how to form the Cartesian product of a set of lists. That is, given a list like,

`   { { a b c } { d e f } }`

he wanted

`   {{a d} {a e} {a f} {b d} {b e} {b f} {c d} {c e} {c f}}`

He also wanted it to generalize to higher dimension: given

`   {{a b} {c d} {e f}}`

he wanted

`   {{a c e} {a c f} {a d e} {a d f} {b c e} {b c f} {b d e} {b d f}}`

and so on.

Kevin Kenny proposed the following:

``` proc crossProduct { listOfLists } {
if { [llength \$listOfLists] == 0 } {
return [list [list]]
} else {
set result [list]
foreach elt [lindex \$listOfLists 0] {
foreach combination [crossProduct [lrange \$listOfLists 1 end]] {
lappend result [linsert \$combination 0 \$elt]
}
}
return \$result
}
}
puts [crossProduct {{a b c} {d e f} {g h i}}]```

This solution is by no means the fastest available, but it appears to work for the purpose.

KBK 2004-07-28: Note that expanding a large Cartesian product can consume large amounts of memory. It's often more useful to iterate some script for each element of the cross product.

Something like the following code gives a rough approximation of a control structure to do so.

``` proc rforeach { varlist vallist args } {
set i 0
foreach v \$varlist {
set localName x\$[incr i]
lappend localNames \$localName
upvar 1 \$v \$localName
}
foreach \$localNames \$vallist {
if { [llength \$args] <= 1 } {
set status [catch {
uplevel 1 [lindex \$args 0]
} result]
} else {
set status [catch {
uplevel 1 [linsert \$args 0 rforeach_nested]
} result]
}
if { \$status != 0 && \$status != 4 } break
}
switch -exact -- \$status {
0 - 3 - 4 {
return
}
1 {
return -code error -errorcode \$::errorCode \$result
}
2 {
return -code return \$result
}
}
}
proc rforeach_nested { varlist vallist args } {
set i 0
foreach v \$varlist {
set localName x\$[incr i]
lappend localNames \$localName
upvar 1 \$v \$localName
}
foreach \$localNames \$vallist {
if { [llength \$args] <= 1 } {
set status [catch {
uplevel 1 [lindex \$args 0]
} result]
} else {
set status [catch {
uplevel 1 [linsert \$args 0 rforeach_nested]
} result]
}
if { \$status != 0 && \$status != 4 } break
}
switch -exact -- \$status {
0 - 4 {
return
}
1 {
return -code error -errorcode \$::errorCode \$result
}
2 {
return -code return \$result
}
3 {
return -code break
}
}
}
rforeach a {a1 a2} b {b1 b2 b3} {c d} {c1 d1 c2 d2} e e1 {
puts [list \$a \$b \$c \$d \$e]
if { \$b eq {b3} } continue
puts "b isn't b3; didn't continue"
if { \$a eq {a2} } break
puts "a isn't a2; didn't break"
}```

Eric Boudaillier 2004-07-29: I also needed such procedure to generate test code and wrote the following procedure, which build the foreach imbrication script and evaluate it:

``` proc forall {args} {
if {[llength \$args] < 3 || [llength \$args] % 2 == 0} {
return -code error "wrong \# args: should be \"forall varList list ?varList list ...? body\""
}
set body [lindex \$args end]
set args [lrange \$args 0 end-1]
while {[llength \$args]} {
set varName [lindex \$args end-1]
set list    [lindex \$args end]
set args    [lrange \$args 0 end-2]
set body    [list foreach \$varName \$list \$body]
}
uplevel 1 \$body
}```

Arjen Markus An interesting variation on this theme: how to generate the set of subsets containing 1, 2, 3 ... elements. For example:

`   {a b c d e}`

will give rise to:

```   {{a} {b} {c} {d} {e}}
{{a b} {a c} {a d} {a e} {b c} {b d} {b e} {c d} {c e} {d e}}
...```

It does not seem quite trivial.

The answer is posted in Power set of a list.

Category Mathematics