Hi,
I'm trying to find an efficient and declarative way of computing the cartesian
product of sets represented by a list of lists.
For example, given a list [[1 2] [3] [4 6]]
return [[1 3 4] [1 3 6] [2 3 4] [2 3 6]]
for any arbitrary list of lists.
I found a solution, but it doesn't seem to be efficient and it produces
duplicates of the elements of the output list. Does anybody know a good way of
doing it?
Here is the code:
fun {CartesianProduct List}
fun {AddFirst List F}
case List of nil then nil
[] H|T then
{Append [F] H}|{AddFirst T F}
end
end
Remain Part1 in
case List of nil then nil
[] H|T then
case H of nil then nil
[] H2|T2 then
if T2==nil then Remain = nil
else Remain = T2|T end
if {CartesianProduct T}==nil then
Part1 = {Map {MakeList {Length H}} fun{$ A} [H2] end}
else Part1 = {AddFirst {CartesianProduct T} H2}
end
{Append Part1 {CartesianProduct Remain}}
end
end
end
Thanks for your help,
François Mairesse
-
Please send submissions to users@mozart-oz.org
and administriva mail to users-request@mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.
Please send bug reports to bugs@mozart-oz.org.