Version 0 of Cartesian product of a list of lists

Updated 2001-11-15 23:57:31

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.