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.
There are two approaches, depending on whether you need all the sets of subsets.
Kevin Kenny replies: 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]
}