Cartesian product of two or more lists

From Rosetta Code
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[edit]

-- 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
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#[edit]

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 }));
}
}
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:

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)}}}");
}
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[edit]

Various routes can be taken to Cartesian products in Haskell. For the product of two lists we could write:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys =
[ (x, y)
| x <- xs
, y <- ys ]

more directly:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x, y)]

applicatively:

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

parsimoniously:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = (<*>) . fmap (,)

We might test any of these with:

main :: IO ()
main =
mapM_ print $
uncurry cartProd <$>
[([1, 2], [3, 4]), ([3, 4], [1, 2]), ([1, 2], []), ([], [1, 2])]
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,

cartProdN :: [[a]] -> [[a]]
cartProdN = sequence
 
main :: IO ()
main = print $ cartProdN [[1, 2], [3, 4], [5, 6]]
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:

cartProdN :: [[a]] -> [[a]]
cartProdN = foldr (\xs as -> xs >>= \x -> as >>= \a -> [x : a]) [[]]

or, equivalently, as:

cartProdN :: [[a]] -> [[a]]
cartProdN = foldr
(\xs as ->
[ x : a
| x <- xs
, a <- as ])
[[]]

testing any of these with something like:

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]]
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[edit]

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).

   { 1776 1789 ; 7 12 ; 4 14 23 ; 0 1   NB. result is 4 dimensional array with shape 2 2 3 2
┌────────────┬────────────┐
1776 7 4 01776 7 4 1
├────────────┼────────────┤
1776 7 14 01776 7 14 1
├────────────┼────────────┤
1776 7 23 01776 7 23 1
└────────────┴────────────┘
 
┌────────────┬────────────┐
1776 12 4 01776 12 4 1
├────────────┼────────────┤
1776 12 14 01776 12 14 1
├────────────┼────────────┤
1776 12 23 01776 12 23 1
└────────────┴────────────┘
 
 
┌────────────┬────────────┐
1789 7 4 01789 7 4 1
├────────────┼────────────┤
1789 7 14 01789 7 14 1
├────────────┼────────────┤
1789 7 23 01789 7 23 1
└────────────┴────────────┘
 
┌────────────┬────────────┐
1789 12 4 01789 12 4 1
├────────────┼────────────┤
1789 12 14 01789 12 14 1
├────────────┼────────────┤
1789 12 23 01789 12 23 1
└────────────┴────────────┘
{ 1 2 3 ; 30 ; 50 100 NB. result is a 2-dimensional array with shape 2 3
┌───────┬────────┐
1 30 501 30 100
├───────┼────────┤
2 30 502 30 100
├───────┼────────┤
3 30 503 30 100
└───────┴────────┘
{ 1 2 3 ; '' ; 50 100 NB. result is an empty 3-dimensional array with shape 3 0 2
 

JavaScript[edit]

ES6[edit]

Functional[edit]

Cartesian products fall quite naturally out of concatMap, and its argument-flipped twin bind.

For the Cartesian product of just two lists:

(() => {
 
// 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]),
]));
})();
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:

(() => {
// 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]
]))
])
})();
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[edit]

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:

(() => {
// 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]
]))
]);
})();
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[edit]

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:

 
def products: .[0][] as $x | .[1][] as $y | [$x,$y];
 

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:

 
def product: [products];
 

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

 
[[1,2], []] | product
 

produces:

[]

n-way Cartesian Product[edit]

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

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

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

Julia[edit]

 
# Product {1, 2} × {3, 4}
collect(product([1, 2], [3, 4]))
# Product {3, 4} × {1, 2}
collect(product([3, 4], [1, 2]))
 
# Product {1, 2} × {}
collect(product([1, 2], []))
# Product {} × {1, 2}
collect(product([], [1, 2]))
 
# Product {1776, 1789} × {7, 12} × {4, 14, 23} × {0, 1}
collect(product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]))
# Product {1, 2, 3} × {30} × {500, 100}
collect(product([1, 2, 3], [30], [500, 100]))
# Product {1, 2, 3} × {} × {500, 100}
collect(product([1, 2, 3], [], [500, 100]))
 

Kotlin[edit]

// 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()}")
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')))
}
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]
]

Lua[edit]

An iterator is created to output the product items.

  local pk,upk = table.pack, table.unpack
local getn = function(t)return #t end
local const = function(k)return function(e) return k end end
local function attachIdx(f)-- one-time-off function modifier
local idx = 0
return function(e)idx=idx+1 ; return f(e,idx)end
end
 
local function reduce(t,acc,f)
for i=1,t.n or #t do acc=f(acc,t[i])end
return acc
end
local function imap(t,f)
local r = {n=t.n or #t, r=reduce, u=upk, m=imap}
for i=1,r.n do r[i]=f(t[i])end
return r
end
 
local function prod(...)
local ts = pk(...)
local limit = imap(ts,getn)
local idx, cnt = imap(limit,const(1)), 0
local max = reduce(limit,1,function(a,b)return a*b end)
local function ret(t,i)return t[idx[i]] end
return function()
if cnt>=max then return end -- no more output
if cnt==0 then -- skip for 1st
cnt = cnt + 1
else
cnt, idx[#idx] = cnt + 1, idx[#idx] + 1
for i=#idx,2,-1 do -- update index list
if idx[i]<=limit[i] then
break -- no further update need
else -- propagate limit overflow
idx[i],idx[i-1] = 1, idx[i-1]+1
end
end
end
return cnt,imap(ts,attachIdx(ret)):u()
end
end
--- test
for i,a,b in prod({1,2},{3,4}) do
print(i,a,b)
end
print()
for i,a,b in prod({3,4},{1,2}) do
print(i,a,b)
end
 
Output:
1	1	3
2	1	4
3	2	3
4	2	4

1	3	1
2	3	2
3	4	1
4	4	2

Maple[edit]

 
cartmulti := proc ()
local m, v;
if [] in {args} then
return [];
else
m := Iterator:-CartesianProduct(args);
for v in m do
printf("%{}a\n", v);
end do;
end if;
end proc;
 

Perl 6[edit]

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

# 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 );
 
# cartesian product of variable number of lists using
# 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);
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))
()

PicoLisp[edit]

(de 2lists (L1 L2)
(mapcan
'((I)
(mapcar
'((A) ((if (atom A) list cons) I A))
L2 ) )
L1 ) )
(de reduce (L . @)
(ifn (rest) L (2lists L (apply reduce (rest)))) )
(de cartesian (L . @)
(and L (rest) (pass reduce L)) )
 
(println
(cartesian (1 2)) )
(println
(cartesian NIL (1 2)) )
(println
(cartesian (1 2) (3 4)) )
(println
(cartesian (3 4) (1 2)) )
(println
(cartesian (1776 1789) (7 12) (4 14 23) (0 1)) )
(println
(cartesian (1 2 3) (30) (500 100)) )
(println
(cartesian (1 2 3) NIL (500 100)) )
Output:
NIL
NIL
((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))
NIL

Python[edit]

Using itertools:

 
import itertools
lists_1 = [[1,2],[3,4]]
lists_2 = [[3,4],[1,2]]
for element in itertools.product(*lists_1):
print(element)
print()
for element in itertools.product(*lists_2):
print(element)
 

Output:

(1, 3)
(1, 4)
(2, 3)
(2, 4)

(3, 1)
(3, 2)
(4, 1)
(4, 2)

Racket[edit]

Racket has a built-in "cartesian-product" function:

#lang racket/base
(require rackunit
 ;; usually, included in "racket", but we're using racket/base so we
 ;; show where this comes from
(only-in racket/list cartesian-product))
;; these tests will pass silently
(check-equal? (cartesian-product '(1 2) '(3 4))
'((1 3) (1 4) (2 3) (2 4)))
(check-equal? (cartesian-product '(3 4) '(1 2))
'((3 1) (3 2) (4 1) (4 2)))
(check-equal? (cartesian-product '(1 2) '()) '())
(check-equal? (cartesian-product '() '(1 2)) '())
 
;; these will print
(cartesian-product '(1776 1789) '(7 12) '(4 14 23) '(0 1))
(cartesian-product '(1 2 3) '(30) '(500 100))
(cartesian-product '(1 2 3) '() '(500 100))
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))
'()

REXX[edit]

/*REXX program  calculates  the   Cartesian product   of two  arbitrary-sized  lists.   */
@.= /*assign the default value to @. array*/
parse arg @.1 /*obtain the optional value of @.1 */
if @.1='' then do; @.1= "{1,2} {3,4}" /*Not specified? Then use the defaults*/
@.2= "{3,4} {1,2}" /* " " " " " " */
@.3= "{1,2} {}" /* " " " " " " */
@.4= "{} {3,4}" /* " " " " " " */
@.5= "{1,2} {3,4,5}" /* " " " " " " */
end
/* [↓] process each of the @.n values*/
do n=1 while @.n \= '' /*keep processing while there's a value*/
z=translate(space(@.n, 0),, ',') /*translate the commas to blanks. */
do #=1 until z=='' /*process each elements in first list. */
parse var z '{' x.# '}' z /*parse the list (contains elements). */
end /*#*/
$=
do i=1 for #-1 /*process the subsequent lists. */
do ii=1 for words(x.i) /*obtain the elements of the first list*/
do j=i+1 for #-1 /*obtain the subsequent lists. */
do jj=1 for words(x.j) /*obtain da elements of subsequent list*/
$=$',('word(x.i, ii)","word(x.j, jj)')' /*append product to $.*/
end /*jj*/
end /*j */
end /*ii*/
end /*i */
say 'Cartesian product of ' space(@.n) " is ───► {"substr($, 2)'}'
end /*n */ /*stick a fork in it, we're all done. */
output   when using the default lists:
Cartesian product of  {1,2} {3,4}  is ───► {(1,3),(1,4),(2,3),(2,4)}
Cartesian product of  {3,4} {1,2}  is ───► {(3,1),(3,2),(4,1),(4,2)}
Cartesian product of  {1,2} {}  is ───► {}
Cartesian product of  {} {3,4}  is ───► {}
Cartesian product of  {1,2} {3,4,5}  is ───► {(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)}

Ruby[edit]

"product" is a method of arrays. It takes one or more arrays as argument and results in the Cartesian product:

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])
 
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]] []

Scala[edit]

Function returning the n-ary product of an arbitrary number of lists, each of arbitrary length:

def cartesianProduct[T](lst: List[T]*): List[List[T]] = {
 
/**
* Prepend single element to all lists of list
* @param e single elemetn
* @param ll list of list
* @param a accumulator for tail recursive implementation
* @return list of lists with prepended element e
*/

def pel(e: T,
ll: List[List[T]],
a: List[List[T]] = Nil): List[List[T]] =
ll match {
case Nil => a.reverse
case x :: xs => pel(e, xs, (e :: x) :: a )
}
 
lst.toList match {
case Nil => Nil
case x :: Nil => List(x)
case x :: _ =>
x match {
case Nil => Nil
case _ =>
lst.par.foldRight(List(x))( (l, a) =>
l.flatMap(pel(_, a))
).map(_.dropRight(x.size))
}
}
}

and usage:

cartesianProduct(List(1, 2), List(3, 4))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
Output:
{(1, 3), (1, 4), (2, 3), (2, 4)}
cartesianProduct(List(3, 4), List(1, 2))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
Output:
{(3, 1), (3, 2), (4, 1), (4, 2)}
cartesianProduct(List(1, 2), List.empty)
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
Output:
{}
cartesianProduct(List.empty, List(1, 2))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
Output:
{}
cartesianProduct(List(1776, 1789), List(7, 12), List(4, 14, 23), List(0, 1))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
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)}
cartesianProduct(List(1, 2, 3), List(30), List(500, 100))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")
Output:
{(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)}
cartesianProduct(List(1, 2, 3), List.empty, List(500, 100))
.map(_.mkString("[", ", ", "]")).mkString("\n")
Output:
{}

Sidef[edit]

In Sidef, the Cartesian product of an arbitrary number of arrays is built-in as Array.cartesian():

cartesian([[1,2], [3,4], [5,6]]).say
cartesian([[1,2], [3,4], [5,6]], {|*arr| say arr })

Alternatively, a simple recursive implementation:

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
}

Completing the task:

say cartesian_product([1,2], [3,4])
say cartesian_product([3,4], [1,2])
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:

say cartesian_product([1,2], [])
say cartesian_product([], [1,2])
Output:
[]
[]

Extra credit:

cartesian_product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]).each{ .say }
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]
say cartesian_product([1, 2, 3], [30], [500, 100])
say cartesian_product([1, 2, 3], [], [500, 100])
Output:
[[1, 30, 500], [1, 30, 100], [2, 30, 500], [2, 30, 100], [3, 30, 500], [3, 30, 100]]
[]

Standard ML[edit]

fun prodList (nil,     _) = nil
| prodList ((x::xs), ys) = map (fn y => (x,y)) ys @ prodList (xs, ys)
 
fun naryProdList zs = foldl (fn (xs, ys) => map op:: (prodList (xs, ys))) [[]] (rev zs)
Output:
- prodList ([1, 2], [3, 4]);
val it = [(1,3),(1,4),(2,3),(2,4)] : (int * int) list
- prodList ([3, 4], [1, 2]);
val it = [(3,1),(3,2),(4,1),(4,2)] : (int * int) list
- prodList ([1, 2], []);
stdIn:8.1-8.22 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val it = [] : (int * ?.X1) list
- naryProdList [[1776, 1789], [7, 12], [4, 14, 23], [0, 1]];
val it =
  [[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]]
  : int list list
- naryProdList [[1, 2, 3], [30], [500, 100]];
val it = [[1,30,500],[1,30,100],[2,30,500],[2,30,100],[3,30,500],[3,30,100]]
  : int list list
- naryProdList [[1, 2, 3], [], [500, 100]];
val it = [] : int list list

Stata[edit]

In Stata, the command fillin may be used to expand a dataset with all combinations of a number of variables. Thus it's easy to compute a cartesian product.

. list
 
+-------+
| a b |
|-------|
1. | 1 3 |
2. | 2 4 |
+-------+
 
. fillin a b
. list
 
+-----------------+
| a b _fillin |
|-----------------|
1. | 1 3 0 |
2. | 1 4 1 |
3. | 2 3 1 |
4. | 2 4 0 |
+-----------------+

The other way around:

. list
 
+-------+
| a b |
|-------|
1. | 3 1 |
2. | 4 2 |
+-------+
 
. fillin a b
. list
 
+-----------------+
| a b _fillin |
|-----------------|
1. | 3 1 0 |
2. | 3 2 1 |
3. | 4 1 1 |
4. | 4 2 0 |
+-----------------+

Note, however, that this is not equivalent to a cartesian product when one of the variables is "empty" (that is, only contains missing values).

. list
 
+-------+
| a b |
|-------|
1. | 1 . |
2. | 2 . |
+-------+
 
. fillin a b
. list
 
+-----------------+
| a b _fillin |
|-----------------|
1. | 1 . 0 |
2. | 2 . 0 |
+-----------------+

This command works also if the varaibles have different numbers of nonmissing elements. However, this requires additional code to remove the observations with missing values.

. list
 
+-----------+
| a b c |
|-----------|
1. | 1 4 6 |
2. | 2 5 . |
3. | 3 . . |
+-----------+
 
. fillin a b c
. list
 
+---------------------+
| a b c _fillin |
|---------------------|
1. | 1 4 6 0 |
2. | 1 4 . 1 |
3. | 1 5 6 1 |
4. | 1 5 . 1 |
5. | 1 . 6 1 |
|---------------------|
6. | 1 . . 1 |
7. | 2 4 6 1 |
8. | 2 4 . 1 |
9. | 2 5 6 1 |
10. | 2 5 . 0 |
|---------------------|
11. | 2 . 6 1 |
12. | 2 . . 1 |
13. | 3 4 6 1 |
14. | 3 4 . 1 |
15. | 3 5 6 1 |
|---------------------|
16. | 3 5 . 1 |
17. | 3 . 6 1 |
18. | 3 . . 0 |
+---------------------+
 
. foreach var of varlist _all {
quietly drop if missing(`var')
}
 
. list
 
+---------------------+
| a b c _fillin |
|---------------------|
1. | 1 4 6 0 |
2. | 1 5 6 1 |
3. | 2 4 6 1 |
4. | 2 5 6 1 |
5. | 3 4 6 1 |
|---------------------|
6. | 3 5 6 1 |
+---------------------+

zkl[edit]

Cartesian product is build into iterators or can be done with nested loops.

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))

The walk method will throw an error if used on an empty iterator but the pump method doesn't.

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()
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()