Rolf Ade boasted 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.
----
[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]