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.
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.
Kevin Kenny replies: There are two approaches, depending on whether you need all the sets of subsets.
If you want to generate all the sets at once, the easiest way by far is to enumerate the power set and collate the subsets by size.
proc subsets { list } {
# Check list size
if { [llength $list] > 32 } {
error "You don't really expect to list all 2**[llength $list] subsets, do you?"
}
# Calculate total number of subsets
set n [expr { 1 << [llength $list] }]
# Enumerate the subsets. If the list is { a b c }, then element
# 0 is the empty set, 1 is the set { a }, 2 is the set { b },
# 3 is { a b }, 4 is { c }, 5 is { a c }, 6 is { b c }, and 7
# is { a b c }.
for { set i 0 } { $i < $n } { incr i } {
set subset {}
for { set j 0 } { $j < [llength $list] } { incr j } {
if { $i & ( 1 << $j ) } {
lappend subset [lindex $list $j]
}
}
# Markus asks for subsets to be sorted out by size. Collate
# them into arrays.
lappend subsets([llength $subset]) $subset
}
set retval {}
for { set k 0 } { $k <= [llength $list] } { incr k } {
lappend retval $subsets($k)
}
return $retval
}
puts [join [subsets { a b c d }] \n]If you really want to enumerate the combinations of the elements of $list taken $size at a time, then it is fairly trivial to enumerate them recursively:
proc subsets2 { list size } {
if { $size == 0 } {
return [list [list]]
}
set retval {}
for { set i 0 } { ($i + $size) <= [llength $list] } { incr i } {
set firstElement [lindex $list $i]
set remainingElements [lrange $list [expr { $i + 1 }] end]
foreach subset [subsets2 $remainingElements [expr { $size - 1 }]] {
lappend retval [linsert $subset 0 $firstElement]
}
}
return $retval
}
for { set i 0 } { $i <= 4 } { incr i } {
puts [subsets2 {a b c d} $i]
}