Cartesian product of two or more lists: Difference between revisions
Content added Content deleted
Drkameleon (talk | contribs) (Added Arturo implementation) |
(→{{header|Lua}}: added another Lua solution) |
||
Line 2,704: | Line 2,704: | ||
end |
end |
||
end</lang> |
end</lang> |
||
=== Functional-esque (non-iterator) === |
|||
Motivation: If a list-of-lists is passed into the cartesian product, then wouldn't a list-of-lists be the expected return type? Of course this is just personal opinion/preference, other implementations are fine as-is if you'd rather have an iterator. |
|||
<lang lua>-- support: |
|||
function T(t) return setmetatable(t, {__index=table}) end |
|||
table.clone = function(t) local s=T{} for k,v in ipairs(t) do s[k]=v end return s end |
|||
table.reduce = function(t,f,acc) for i=1,#t do acc=f(t[i],acc) end return acc end |
|||
-- implementation: |
|||
local function cartprod(sets) |
|||
local temp, prod = T{}, T{} |
|||
local function descend(depth) |
|||
for _,v in ipairs(sets[depth]) do |
|||
temp[depth] = v |
|||
if (depth==#sets) then prod[#prod+1]=temp:clone() else descend(depth+1) end |
|||
end |
|||
end |
|||
descend(1) |
|||
return prod |
|||
end |
|||
-- demonstration: |
|||
tests = { |
|||
{ {1, 2}, {3, 4} }, |
|||
{ {3, 4}, {1, 2} }, |
|||
{ {1, 2}, {} }, |
|||
{ {}, {1, 2} }, |
|||
{ {1776, 1789}, {7, 12}, {4, 14, 23}, {0, 1} }, |
|||
{ {1, 2, 3}, {30}, {500, 100} }, |
|||
{ {1, 2, 3}, {}, {500, 100} } |
|||
} |
|||
for _,test in ipairs(tests) do |
|||
local cp = cartprod(test) |
|||
print("{"..cp:reduce(function(t,a) return (a=="" and a or a..", ").."("..t:concat(", ")..")" end,"").."}") |
|||
end</lang> |
|||
{{out}} |
|||
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)} |
|||
{(3, 1), (3, 2), (4, 1), (4, 2)} |
|||
{} |
|||
{} |
|||
{(1776, 7, 4, 0), (1776, 7, 4, 1), (1776, 7, 14, 0), (1776, 7, 14, 1), (1776, 7, 23, 0), (1776, 7, 23, 1), (1776, 12, 4, 0), (1776, 12, 4, 1), (1776, 12, 14, 0), (1776, 12, 14, 1), (1776, 12, 23, 0), (1776, 12, 23, 1), (1789, 7, 4, 0), (1789, 7, 4, 1), (1789, 7, 14, 0), (1789, 7, 14, 1), (1789, 7, 23, 0), (1789, 7, 23, 1), (1789, 12, 4, 0), (1789, 12, 4, 1), (1789, 12, 14, 0), (1789, 12, 14, 1), (1789, 12, 23, 0), (1789, 12, 23, 1)} |
|||
{(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)} |
|||
{}</pre> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |