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

Updated 2002-01-03 16:09:47

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]
}```

Category Mathematics