Cartesian product of two or more lists: Difference between revisions

From Rosetta Code
Content added Content deleted
(updated python implementation)
(jq)
Line 672: Line 672:


[]</pre>
[]</pre>

=={{header|jq}}==

jq is stream-oriented and so we begin by defining a function that will emit a stream of the elements of the Cartesian product of two arrays:
<lang jq>
def products: .[0][] as $x | .[1][] as $y | [$x,$y];
</lang>

To generate an array of these arrays, one would in practice most likely simply write `[products]`, but to comply with the requirements of this article, we can define `product` as:
<lang jq>
def product: [products];
</lang>

For the sake of brevity, two illustrations should suffice:

[ [1,2], [3,4] ] | products

produces the stream:
<pre>
[1,3]
[1,4]
[2,3]
[2,4]
</pre>

And
<lang jq>
[[1,2], []] | product
</lang>
produces:
<pre>
[]
</pre>

===n-way Cartesian Product===
Given an array of two or more arrays as input, `cartesians` as defined here produces a stream of the components of their Cartesian product:

<lang jq>
def cartesians:
if length <= 2 then products
else .[0][] as $x
| (.[1:] | cartesians) as $y
| [$x] + $y
end;
</lang>

Again for brevity, in the following, we will just show the number of items in the Cartesian products:

[ [1776, 1789], [7, 12], [4, 14, 23], [0, 1]] | [cartesians] | length
# 24

[[1, 2, 3], [30], [500, 100] ] | [cartesians] | length
# 6

[[1, 2, 3], [], [500, 100] ] | [cartesians] | length
# 0


=={{header|Kotlin}}==
=={{header|Kotlin}}==

Revision as of 05:26, 10 July 2017

Task
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]]

[]

C#

<lang csharp>using System; public class Program { 

   public static void Main()
   {
       int[] empty = new int[0];
       int[] list1 = { 1, 2 };
       int[] list2 = { 3, 4 };
       int[] list3 = { 1776, 1789 };
       int[] list4 = { 7, 12 };
       int[] list5 = { 4, 14, 23 };
       int[] list6 = { 0, 1 };
       int[] list7 = { 1, 2, 3 };
       int[] list8 = { 30 };
       int[] list9 = { 500, 100 };
       
       foreach (var sequenceList in new [] {
           new [] { list1, list2 },
           new [] { list2, list1 },
           new [] { list1, empty },
           new [] { empty, list1 },
           new [] { list3, list4, list5, list6 },
           new [] { list7, list8, list9 },
           new [] { list7, empty, list9 }
       }) {
           var cart = sequenceList.CartesianProduct()
               .Select(tuple => $"({string.Join(", ", tuple)})");
           Console.WriteLine($"{{{string.Join(", ", cart)}}}");
       }
   }

}

public static class Extensions { 

   public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) {
       IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
       return sequences.Aggregate(
           emptyProduct,
           (accumulator, sequence) =>
           from acc in accumulator
           from item in sequence
           select acc.Concat(new [] { item }));
   }

}</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)}
{}

If the number of lists is known, LINQ provides an easier solution: <lang csharp>public static void Main() { 

   ///...
   var cart1 =
       from a in list1
       from b in list2
       select (a, b); // C# 7.0 tuple
   Console.WriteLine($"{{{string.Join(", ", cart1)}}}");
       
   var cart2 =
       from a in list7
       from b in list8
       from c in list9
       select (a, b, c);
   Console.WriteLine($"{{{string.Join(", ", cart2)}}}");

}</lang>

Output:
{(1, 3), (1, 4), (2, 3), (2, 4)}
{(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] -> [b] -> [(a, b)] cartProd xs ys = 

 [ (x, y)
 | x <- xs 
 , y <- ys ]</lang>

more directly: <lang Haskell>cartProd :: [a] -> [b] -> [(a, b)] cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x, y)]</lang>

applicatively: <lang Haskell>cartProd :: [a] -> [b] -> [(a, b)] cartProd xs ys = (,) <$> xs <*> ys</lang>

parsimoniously: <lang Haskell>cartProd :: [a] -> [b] -> [(a, b)] cartProd = (<*>) . fmap (,)</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 x = subList[j],
                   k = acc.length;
               while (k--) ps.push([x].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]]

[]

jq

jq is stream-oriented and so we begin by defining a function that will emit a stream of the elements of the Cartesian product of two arrays: <lang jq> def products: .[0][] as $x | .[1][] as $y | [$x,$y]; </lang>

To generate an array of these arrays, one would in practice most likely simply write `[products]`, but to comply with the requirements of this article, we can define `product` as: <lang jq> def product: [products]; </lang>

For the sake of brevity, two illustrations should suffice: 

   [ [1,2], [3,4] ] | products

produces the stream: 

 [1,3]
 [1,4]
 [2,3]
 [2,4]

And <lang jq> [[1,2], []] | product </lang> produces: 

[]

n-way Cartesian Product

Given an array of two or more arrays as input, `cartesians` as defined here produces a stream of the components of their Cartesian product:

<lang jq> def cartesians: 

 if length <= 2 then products
 else .[0][] as $x
 | (.[1:] | cartesians) as $y
 | [$x] + $y
 end;

</lang>

Again for brevity, in the following, we will just show the number of items in the Cartesian products: 

   [ [1776, 1789], [7, 12], [4, 14, 23], [0, 1]] | [cartesians] | length
   # 24

   [[1, 2, 3], [30], [500, 100] ] | [cartesians] | length
   # 6

   [[1, 2, 3], [], [500, 100] ] | [cartesians] | length
   # 0

Kotlin

<lang scala>// version 1.1.2

fun flattenList(nestList: List<Any>): List<Any> { 

   val flatList = mutableListOf<Any>()

   fun flatten(list: List<Any>) {
       for (e in list) {
           if (e !is List<*>)
               flatList.add(e)
           else
               @Suppress("UNCHECKED_CAST")
               flatten(e as List<Any>)
       }
   } 

   flatten(nestList)   
   return flatList

}

operator fun List<Any>.times(other: List<Any>): List<List<Any>> { 

   val prod = mutableListOf<List<Any>>()
   for (e in this) {
       for (f in other) {
           prod.add(listOf(e, f))
       }
   }
   return prod

}

fun nAryCartesianProduct(lists: List<List<Any>>): List<List<Any>> { 

   require(lists.size >= 2)
   return lists.drop(2).fold(lists[0] * lists[1]) { cp, ls -> cp * ls }.map { flattenList(it) }

}

fun printNAryProduct(lists: List<List<Any>>) { 

   println("${lists.joinToString(" x ")} = ")
   println("[")
   println("${nAryCartesianProduct(lists).joinToString("\n    ", "    ")}")
   println("]\n")

}

fun main(args: Array<String>) { 

  println("[1, 2] x [3, 4] = ${listOf(1, 2) * listOf(3, 4)}")
  println("[3, 4] x [1, 2] = ${listOf(3, 4) * listOf(1, 2)}")
  println("[1, 2] x []     = ${listOf(1, 2) * listOf<Any>()}")
  println("[]     x [1, 2] = ${listOf<Any>() * listOf(1, 2)}")
  println("[1, a] x [2, b] = ${listOf(1, 'a') * listOf(2, 'b')}")
  println()
  printNAryProduct(listOf(listOf(1776, 1789), listOf(7, 12), listOf(4, 14, 23), listOf(0, 1)))
  printNAryProduct(listOf(listOf(1, 2, 3), listOf(30), listOf(500, 100)))
  printNAryProduct(listOf(listOf(1, 2, 3), listOf<Int>(), listOf(500, 100)))
  printNAryProduct(listOf(listOf(1, 2, 3), listOf(30), listOf('a', 'b')))

}</lang>

Output:
[1, 2] x [3, 4] = [[1, 3], [1, 4], [2, 3], [2, 4]]
[3, 4] x [1, 2] = [[3, 1], [3, 2], [4, 1], [4, 2]]
[1, 2] x []     = []
[]     x [1, 2] = []
[1, a] x [2, b] = [[1, 2], [1, b], [a, 2], [a, b]]

[1776, 1789] x [7, 12] x [4, 14, 23] x [0, 1] = 
[
    [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] x [30] x [500, 100] = 
[
    [1, 30, 500]
    [1, 30, 100]
    [2, 30, 500]
    [2, 30, 100]
    [3, 30, 500]
    [3, 30, 100]
]

[1, 2, 3] x [] x [500, 100] = 
[
    
]

[1, 2, 3] x [30] x [a, b] = 
[
    [1, 30, a]
    [1, 30, b]
    [2, 30, a]
    [2, 30, b]
    [3, 30, a]
    [3, 30, b]
]

Perl 6

Works with: Rakudo version 2017.06

The cross meta operator X will return the cartesian product of two lists. To apply the cross meta-operator to a variable number of lists, use the hyper cross meta operator [X].

<lang perl6># cartesian product of two lists using the X cross meta-operator say (1, 2) X (3, 4); say (3, 4) X (1, 2); say (1, 2) X ( ); say ( ) X ( 1, 2 );

  1. cartesian product of variable number of lists using
  2. the [X] hyper cross meta-operator

say [X] (1776, 1789), (7, 12), (4, 14, 23), (0, 1); say [X] (1, 2, 3), (30), (500, 100); say [X] (1, 2, 3), (), (500, 100);</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))
()

Python

Using itertools: <lang python> import itertools lists_1 = [[1,2],[3,4]] lists_2 = [[1,2],[3,4]] for element in itertools.product(*lists_1): 

   print(element)

for element in itertools.product(*lists_2): 

   print(element)

</lang>

Ruby

"product" is a method of arrays. It takes one or more arrays as argument and results in the Cartesian product: <lang ruby>p [1, 2].product([3, 4]) p [3, 4].product([1, 2]) p [1, 2].product([]) p [].product([1, 2]) p [1776, 1789].product([7, 12], [4, 14, 23], [0, 1]) p [1, 2, 3].product([30], [500, 100]) p [1, 2, 3].product([], [500, 100]) </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]]
[]

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>

Retrieved from "https://rosettacode.org/wiki/Cartesian_product_of_two_or_more_lists?oldid=275852"