Cartesian product of two or more lists: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl6 example) |
(=={{header|JavaScript}}== ES6 example for the simple case) |
||
Line 20: | Line 20: | ||
:: {1,2,3} × {} × {500, 100} |
:: {1,2,3} × {} × {500, 100} |
||
<br><br> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Various routes can be taken to Cartesian products in Haskell. |
Various routes can be taken to Cartesian products in Haskell. |
||
Line 94: | Line 93: | ||
[[1,30,500],[1,30,100],[2,30,500],[2,30,100],[3,30,500],[3,30,100]] |
[[1,30,500],[1,30,100],[2,30,500],[2,30,100],[3,30,500],[3,30,100]] |
||
[]</pre> |
|||
=={{header|JavaScript}}== |
|||
===ES6=== |
|||
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> |
|||
{{Out}} |
|||
<pre>[[1,3],[1,4],[2,3],[2,4]] |
|||
[[3,1],[3,2],[4,1],[4,2]] |
|||
[] |
|||
[]</pre> |
[]</pre> |
||
Revision as of 16:17, 29 May 2017
- 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}
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>
Or, more directly: <lang Haskell>cartProd :: [a] -> [a] -> [(a, a)] cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x, y)]</lang>
We might test either 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, or we could define ourselves an equivalent function over a list of lists in terms of a fold:
For example as: <lang haskell>foldr (\xs as -> xs >>= \x -> as >>= \a -> [x : a]) [[]]</lang> or, equivalently, as: <lang haskell>foldr
(\xs as -> [ x : a | x <- xs , a <- as ]) [[]]</lang>
<lang haskell>main :: IO () main = do
mapM_ print $ sequence [[1776, 1789], [7,12], [4, 14, 23], [0,1]] putStrLn "" print $ sequence [[1,2,3], [30], [500, 100]] putStrLn "" print $ sequence [[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]] []
JavaScript
ES6
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]] [] []
Perl 6
Nominally the cross meta operator X does this, but doesn't gracefully handle the case of an empty list. We can easily wrap it in a subroutine with appropriate filtering however.
<lang perl6>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: ()