Cartesian product of two or more lists
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Show one or more idiomatic ways of generating the Cartesian product of two arbitrary lists in your language.
Demonstrate that your function/method correctly returns:
- {1, 2} × {3, 4} = {(1, 3), (1, 4), (2, 3), (2, 4)}
and, in contrast:
- {3, 4} × {1, 2} = {(3, 1), (3, 2), (4, 1), (4, 2)}
Also demonstrate, using your function/method, that the product of an empty list with any other list is empty.
- {1, 2} × {} = {}
- {} × {1, 2} = {}
For extra credit, show or write a function returning the n-ary product of an arbitrary number of lists, each of arbitrary length. Your function might, for example, accept a single argument which is itself a list of lists, and return the n-ary product of those lists.
Use your n-ary Cartesian product function to show the following products:
- {1776, 1789} × {7, 12} × {4, 14, 23} × {0, 1}
- {1, 2, 3} × {30} × {500, 100}
- {1, 2, 3} × {} × {500, 100}
AppleScript
<lang AppleScript>-- CARTESIAN PRODUCTS ---------------------------------------------------------
-- Two lists:
-- cartProd :: [a] -> [b] -> [(a, b)] on cartProd(xs, ys)
script
on |λ|(x)
script
on |λ|(y)
x, y
end |λ|
end script
concatMap(result, ys)
end |λ|
end script
concatMap(result, xs)
end cartProd
-- N-ary – a function over a list of lists:
-- cartProdNary :: a -> a on cartProdNary(xss)
script
on |λ|(accs, xs)
script
on |λ|(x)
script
on |λ|(a)
{x & a}
end |λ|
end script
concatMap(result, accs)
end |λ|
end script
concatMap(result, xs)
end |λ|
end script
foldr(result, {{}}, xss)
end cartProdNary
-- TESTS ---------------------------------------------------------------------- on run
set baseExamples to unlines(map(show, ¬
[cartProd({1, 2}, {3, 4}), ¬
cartProd({3, 4}, {1, 2}), ¬
cartProd({1, 2}, {}), ¬
cartProd({}, {1, 2})]))
set naryA to unlines(map(show, ¬
cartProdNary([{1776, 1789}, {7, 12}, {4, 14, 23}, {0, 1}])))
set naryB to show(cartProdNary([{1, 2, 3}, {30}, {500, 100}]))
set naryC to show(cartProdNary([{1, 2, 3}, {}, {500, 100}]))
intercalate(linefeed & linefeed, {baseExamples, naryA, naryB, naryC})
end run
-- GENERIC FUNCTIONS ----------------------------------------------------------
-- concatMap :: (a -> [b]) -> [a] -> [b] on concatMap(f, xs)
set lst to {}
set lng to length of xs
tell mReturn(f)
repeat with i from 1 to lng
set lst to (lst & |λ|(item i of xs, i, xs))
end repeat
end tell
return lst
end concatMap
-- foldr :: (a -> b -> a) -> a -> [b] -> a on foldr(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from lng to 1 by -1
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldr
-- intercalate :: Text -> [Text] -> Text on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to lstText as text
set my text item delimiters to dlm
return strJoined
end intercalate
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- show :: a -> String on show(e)
set c to class of e
if c = list then
script serialized
on |λ|(v)
show(v)
end |λ|
end script
"[" & intercalate(", ", map(serialized, e)) & "]"
else if c = record then
script showField
on |λ|(kv)
set {k, ev} to kv
"\"" & k & "\":" & show(ev)
end |λ|
end script
"{" & intercalate(", ", ¬
map(showField, zip(allKeys(e), allValues(e)))) & "}"
else if c = date then
"\"" & iso8601Z(e) & "\""
else if c = text then
"\"" & e & "\""
else if (c = integer or c = real) then
e as text
else if c = class then
"null"
else
try
e as text
on error
("«" & c as text) & "»"
end try
end if
end show
-- unlines :: [String] -> String on unlines(xs)
intercalate(linefeed, xs)
end unlines</lang>
- Output:
[[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]] []
Haskell
Various routes can be taken to Cartesian products in Haskell. For the product of two lists we could write: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys =
[ (x, y) | x <- xs , y <- ys ]</lang>
more directly: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x, y)]</lang>
or, applicatively: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys = (,) <$> xs <*> ys</lang>
We might test any of these with: <lang haskell>main :: IO () main =
mapM_ print $ uncurry cartProd <$> [([1, 2], [3, 4]), ([3, 4], [1, 2]), ([1, 2], []), ([], [1, 2])]</lang>
- Output:
[(1,3),(1,4),(2,3),(2,4)] [(3,1),(3,2),(4,1),(4,2)] [] []
For the n-ary Cartesian product of an arbitrary number of lists, we could apply the Prelude's standard sequence function to a list of lists,
<lang haskell>cartProdN :: a -> a
cartProdN = sequence
main :: IO () main = print $ cartProdN [[1, 2], [3, 4], [5, 6]]</lang>
- Output:
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
or we could define ourselves an equivalent function over a list of lists in terms of a fold, for example as: <lang haskell>cartProdN :: a -> a cartProdN = foldr (\xs as -> xs >>= \x -> as >>= \a -> [x : a]) [[]]</lang> or, equivalently, as: <lang haskell>cartProdN :: a -> a cartProdN = foldr
(\xs as ->
[ x : a
| x <- xs
, a <- as ])
[[]]</lang>
testing any of these with something like: <lang haskell>main :: IO () main = do
mapM_ print $ cartProdN [[1776, 1789], [7,12], [4, 14, 23], [0,1]] putStrLn "" print $ cartProdN [[1,2,3], [30], [500, 100]] putStrLn "" print $ cartProdN [[1,2,3], [], [500, 100]]</lang>
- Output:
[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]] []
J
The J primitive catalogue { forms the Cartesian Product of two or more boxed lists. The result is a multi-dimensional array (which can be reshaped to a simple list of lists if desired).
<lang j> { 1776 1789 ; 7 12 ; 4 14 23 ; 0 1 NB. result is 4 dimensional array with shape 2 2 3 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 2 3 ; 30 ; 50 100 NB. result is a 2-dimensional array with shape 2 3
┌───────┬────────┐ │1 30 50│1 30 100│ ├───────┼────────┤ │2 30 50│2 30 100│ ├───────┼────────┤ │3 30 50│3 30 100│ └───────┴────────┘
{ 1 2 3 ; ; 50 100 NB. result is an empty 3-dimensional array with shape 3 0 2
</lang>
JavaScript
ES6
Functional
Cartesian products fall quite naturally out of concatMap, and its argument-flipped twin bind.
For the Cartesian product of just two lists: <lang JavaScript>(() => {
// CARTESIAN PRODUCT OF TWO LISTS -----------------------------------------
// cartProd :: [a] -> [b] -> a, b const cartProd = (xs, ys) => concatMap((x => concatMap(y => [ [x, y] ], ys)), xs);
// GENERIC FUNCTIONS ------------------------------------------------------
// concatMap :: (a -> [b]) -> [a] -> [b] const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// show :: a -> String const show = x => JSON.stringify(x); //, null, 2);
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
// TEST -------------------------------------------------------------------
return unlines(map(show, [
cartProd([1, 2], [3, 4]),
cartProd([3, 4], [1, 2]),
cartProd([1, 2], []),
cartProd([], [1, 2]),
]));
})();</lang>
- Output:
[[1,3],[1,4],[2,3],[2,4]] [[3,1],[3,2],[4,1],[4,2]] [] []
For the n-ary Cartesian product over a list of lists: <lang JavaScript>(() => {
// n-ary Cartesian product of a list of lists
// cartProdN :: a -> a const cartProdN = lists => foldr((as, xs) => bind(xs, x => bind(as, a => [x.concat(a)])), [ [] ], lists);
// GENERIC FUNCTIONS ------------------------------------------------------
// bind :: [a] -> (a -> [b]) -> [b] const bind = (xs, f) => [].concat.apply([], xs.map(f));
// foldr (a -> b -> b) -> b -> [a] -> b const foldr = (f, a, xs) => xs.reduceRight(f, a);
// intercalate :: String -> [a] -> String const intercalate = (s, xs) => xs.join(s);
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// show :: a -> String const show = x => JSON.stringify(x);
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
// TEST -------------------------------------------------------------------
return intercalate('\n\n', [unlines(map(show, cartProdN([
[1776, 1789],
[7, 12],
[4, 14, 23],
[0, 1]
]))),
show(cartProdN([
[1, 2, 3],
[30],
[50, 100]
])),
show(cartProdN([
[1, 2, 3],
[],
[50, 100]
]))
])
})();</lang>
- Output:
[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,50],[1,30,100],[2,30,50],[2,30,100],[3,30,50],[3,30,100]] []
Imperative
Imperative implementations of Cartesian products are inevitably less compact and direct, but we can certainly write an iterative translation of a fold over nested applications of bind or concatMap:
<lang JavaScript>(() => {
// n-ary Cartesian product of a list of lists // ( Imperative implementation )
// cartProd :: [a] -> [b] -> a, b const cartProd = lists => { let ps = [], acc = [ [] ], i = lists.length; while (i--) { let subList = lists[i], j = subList.length; while (j--) { let xs = subList[j], k = acc.length; while (k--) ps.push([xs].concat(acc[k])) }; acc = ps; ps = []; }; return acc.reverse(); };
// GENERIC FUNCTIONS ------------------------------------------------------
// intercalate :: String -> [a] -> String const intercalate = (s, xs) => xs.join(s);
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// show :: a -> String const show = x => JSON.stringify(x);
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
// TEST -------------------------------------------------------------------
return intercalate('\n\n', [show(cartProd([
[1, 2],
[3, 4]
])),
show(cartProd([
[3, 4],
[1, 2]
])),
show(cartProd([
[1, 2],
[]
])),
show(cartProd([
[],
[1, 2]
])),
unlines(map(show,cartProd([
[1776, 1789],
[7, 12],
[4, 14, 23],
[0, 1]
]))),
show(cartProd([
[1, 2, 3],
[30],
[50, 100]
])),
show(cartProd([
[1, 2, 3],
[],
[50, 100]
]))
]);
})();</lang>
- Output:
[[1,4],[1,3],[2,4],[2,3]] [[3,2],[3,1],[4,2],[4,1]] [] [] [1776,12,4,1] [1776,12,4,0] [1776,12,14,1] [1776,12,14,0] [1776,12,23,1] [1776,12,23,0] [1776,7,4,1] [1776,7,4,0] [1776,7,14,1] [1776,7,14,0] [1776,7,23,1] [1776,7,23,0] [1789,12,4,1] [1789,12,4,0] [1789,12,14,1] [1789,12,14,0] [1789,12,23,1] [1789,12,23,0] [1789,7,4,1] [1789,7,4,0] [1789,7,14,1] [1789,7,14,0] [1789,7,23,1] [1789,7,23,0] [[1,30,50],[1,30,100],[2,30,50],[2,30,100],[3,30,50],[3,30,100]] []
Perl 6
Nominally the cross meta operator X does this, but due to a bug in Rakudo 2017.05, doesn't gracefully handle the case of an empty list. The bug has been reported, found, and fixed in the bleeding edge compiler, and will be in the 2017.06 release. In the meantime, we can easily wrap it in a subroutine with appropriate filtering.
<lang perl6>#sub cartesian-product (**@list) { [X] @list } # Fails on empty lists due to bug in 2017.05
- work-around
sub cartesian-product (**@list) { ( so none(@list».elems) == 0 ) ?? [X] @list !! () }
- Testing various Cartesian products
for
( (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) )
-> $list {
say "\nLists: { $list.perl }\nCartesian Product:";
say cartesian-product( |$list ).List.perl;
}</lang>
- Output:
Lists: $((1, 2), (3, 4)) Cartesian Product: ((1, 3), (1, 4), (2, 3), (2, 4)) Lists: $((3, 4), (1, 2)) Cartesian Product: ((3, 1), (3, 2), (4, 1), (4, 2)) Lists: $((1, 2), ()) Cartesian Product: () Lists: $((), (1, 2)) Cartesian Product: () Lists: $((1776, 1789), (7, 12), (4, 14, 23), (0, 1)) Cartesian Product: ((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)) Lists: $((1, 2, 3), 30, (500, 100)) Cartesian Product: ((1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)) Lists: $((1, 2, 3), (), (500, 100)) Cartesian Product: ()
Sidef
In Sidef, the Cartesian product of an arbitrary number of arrays is built-in as Array.cartesian(): <lang ruby>cartesian([[1,2], [3,4], [5,6]]).say cartesian([[1,2], [3,4], [5,6]], {|*arr| say arr })</lang>
Alternatively, a simple recursive implementation: <lang ruby>func cartesian_product(*arr) {
var c = [] var r = []
func {
if (c.len < arr.len) {
for item in (arr[c.len]) {
c.push(item)
__FUNC__()
c.pop
}
}
else {
r.push([c...])
}
}()
return r
}</lang>
Completing the task: <lang ruby>say cartesian_product([1,2], [3,4]) say cartesian_product([3,4], [1,2])</lang>
- Output:
[[1, 3], [1, 4], [2, 3], [2, 4]] [[3, 1], [3, 2], [4, 1], [4, 2]]
The product of an empty list with any other list is empty: <lang ruby>say cartesian_product([1,2], []) say cartesian_product([], [1,2])</lang>
- Output:
[] []
Extra credit: <lang ruby>cartesian_product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]).each{ .say }</lang>
- Output:
[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]
<lang ruby>say cartesian_product([1, 2, 3], [30], [500, 100]) say cartesian_product([1, 2, 3], [], [500, 100])</lang>
- Output:
[[1, 30, 500], [1, 30, 100], [2, 30, 500], [2, 30, 100], [3, 30, 500], [3, 30, 100]] []
zkl
Cartesian product is build into iterators or can be done with nested loops. <lang zkl>zkl: Walker.cproduct(List(1,2),List(3,4)).walk().println(); L(L(1,3),L(1,4),L(2,3),L(2,4)) zkl: foreach a,b in (List(1,2),List(3,4)){ print("(%d,%d) ".fmt(a,b)) } (1,3) (1,4) (2,3) (2,4)
zkl: Walker.cproduct(List(3,4),List(1,2)).walk().println(); L(L(3,1),L(3,2),L(4,1),L(4,2))</lang>
The walk method will throw an error if used on an empty iterator but the pump method doesn't. <lang zkl>zkl: Walker.cproduct(List(3,4),List).walk().println(); Exception thrown: TheEnd(Ain't no more)
zkl: Walker.cproduct(List(3,4),List).pump(List).println(); L() zkl: Walker.cproduct(List,List(3,4)).pump(List).println(); L()</lang> <lang zkl>zkl: Walker.cproduct(L(1776,1789),L(7,12),L(4,14,23),L(0,1)).walk().println(); L(L(1776,7,4,0),L(1776,7,4,1),L(1776,7,14,0),L(1776,7,14,1),L(1776,7,23,0),L(1776,7,23,1),L(1776,12,4,0),L(1776,12,4,1),L(1776,12,14,0),L(1776,12,14,1),L(1776,12,23,0),L(1776,12,23,1),L(1789,7,4,0),L(1789,7,4,1),L(1789,7,14,0),L(1789,7,14,1),L(1789,7,23,0),L(1789,7,23,1),L(1789,12,4,0),L(1789,12,4,1),...)
zkl: Walker.cproduct(L(1,2,3),L(30),L(500,100)).walk().println(); L(L(1,30,500),L(1,30,100),L(2,30,500),L(2,30,100),L(3,30,500),L(3,30,100))
zkl: Walker.cproduct(L(1,2,3),List,L(500,100)).pump(List).println(); L()</lang>