Cartesian product of two or more lists: Difference between revisions

Content added Content deleted
(Added AutoHotkey)
m (syntax highlighting fixup automation)
Line 24: Line 24:
=={{header|11l}}==
=={{header|11l}}==
{{trans|Go}}
{{trans|Go}}
<lang 11l>F cart_prod(a, b)
<syntaxhighlight lang=11l>F cart_prod(a, b)
V p = [(0, 0)] * (a.len * b.len)
V p = [(0, 0)] * (a.len * b.len)
V i = 0
V i = 0
Line 36: Line 36:
[Int] empty_array
[Int] empty_array
print(cart_prod([1, 2], empty_array))
print(cart_prod([1, 2], empty_array))
print(cart_prod(empty_array, [1, 2]))</lang>
print(cart_prod(empty_array, [1, 2]))</syntaxhighlight>
====Alternative version====
====Alternative version====
<lang 11l>F cart_prod(a, b)
<syntaxhighlight lang=11l>F cart_prod(a, b)
R multiloop(a, b, (aa, bb) -> (aa, bb))</lang>
R multiloop(a, b, (aa, bb) -> (aa, bb))</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 49: Line 49:


=={{header|Action!}}==
=={{header|Action!}}==
<lang Action!>DEFINE MAX_COUNT="10"
<syntaxhighlight lang=Action!>DEFINE MAX_COUNT="10"
DEFINE MAX_RESULT="100"
DEFINE MAX_RESULT="100"


Line 158: Line 158:
a(0)=a8 a(1)=a9 a(2)=a10 Test(a,3) PutE()
a(0)=a8 a(1)=a9 a(2)=a10 Test(a,3) PutE()
a(0)=a8 a(1)=a3 a(2)=a10 Test(a,3)
a(0)=a8 a(1)=a3 a(2)=a10 Test(a,3)
RETURN</lang>
RETURN</syntaxhighlight>
{{out}}
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cartesian_product_of_two_or_more_lists.png Screenshot from Atari 8-bit computer]
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cartesian_product_of_two_or_more_lists.png Screenshot from Atari 8-bit computer]
Line 172: Line 172:


=={{header|Ada}}==
=={{header|Ada}}==
<lang Ada>with Ada.Text_IO; use Ada.Text_Io;
<syntaxhighlight lang=Ada>with Ada.Text_IO; use Ada.Text_Io;
with Ada.Containers.Doubly_Linked_Lists;
with Ada.Containers.Doubly_Linked_Lists;
with Ada.Strings.Fixed;
with Ada.Strings.Fixed;
Line 275: Line 275:


Put (List_1_2_3 * List_Empty * List'(Nil & 500 & 100)); New_Line;
Put (List_1_2_3 * List_Empty * List'(Nil & 500 & 100)); New_Line;
end Cartesian;</lang>
end Cartesian;</syntaxhighlight>
{{out}}
{{out}}
<pre>{(1,3),(1,4),(2,3),(2,4)}
<pre>{(1,3),(1,4),(2,3),(2,4)}
Line 293: Line 293:
a matrix, and the task is asking for a list, you also need to ravel the result.
a matrix, and the task is asking for a list, you also need to ravel the result.


<lang APL>cart ← ,∘.,</lang>
<syntaxhighlight lang=APL>cart ← ,∘.,</syntaxhighlight>


{{out}}
{{out}}
Line 310: Line 310:
list of lists.
list of lists.


<lang APL>nary_cart ← ⊃(,∘.,)/</lang>
<syntaxhighlight lang=APL>nary_cart ← ⊃(,∘.,)/</syntaxhighlight>


{{out}}
{{out}}
Line 353: Line 353:


=={{header|AppleScript}}==
=={{header|AppleScript}}==
<lang AppleScript>-- CARTESIAN PRODUCTS ---------------------------------------------------------
<syntaxhighlight lang=AppleScript>-- CARTESIAN PRODUCTS ---------------------------------------------------------


-- Two lists:
-- Two lists:
Line 512: Line 512:
on unlines(xs)
on unlines(xs)
intercalate(linefeed, xs)
intercalate(linefeed, xs)
end unlines</lang>
end unlines</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
Line 550: Line 550:
=={{header|Arturo}}==
=={{header|Arturo}}==
{{trans|Ruby}}
{{trans|Ruby}}
<lang rebol>loop [
<syntaxhighlight lang=rebol>loop [
[[1 2][3 4]]
[[1 2][3 4]]
[[3 4][1 2]]
[[3 4][1 2]]
Line 560: Line 560:
] 'lst [
] 'lst [
print as.code product.cartesian lst
print as.code product.cartesian lst
]</lang>
]</syntaxhighlight>


{{out}}
{{out}}
Line 573: Line 573:


=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
<lang AutoHotkey>example := [
<syntaxhighlight lang=AutoHotkey>example := [
(join,
(join,
[[1, 2], [3, 4]]
[[1, 2], [3, 4]]
Line 626: Line 626:
oTemp.Push(v)
oTemp.Push(v)
Product.push(oTemp)
Product.push(oTemp)
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
Line 636: Line 636:
[]</pre>
[]</pre>
=={{header|Bracmat}}==
=={{header|Bracmat}}==
<lang Bracmat>( ( mul
<syntaxhighlight lang=Bracmat>( ( mul
= R a b A B
= R a b A B
. :?R
. :?R
Line 670: Line 670:
& out$(cartprod$((.1 2 3) (.30) (.500 100)))
& out$(cartprod$((.1 2 3) (.30) (.500 100)))
& out$(cartprod$((.1 2 3) (.) (.500 100)))
& out$(cartprod$((.1 2 3) (.) (.500 100)))
)</lang>
)</syntaxhighlight>
<pre>. (.1776 7 4 0)
<pre>. (.1776 7 4 0)
(.1776 7 4 1)
(.1776 7 4 1)
Line 706: Line 706:
=={{header|C}}==
=={{header|C}}==
Recursive implementation for computing the Cartesian product of lists. In the pursuit of making it as interactive as possible, the parsing function ended up taking the most space. The product set expression must be supplied enclosed by double quotes. Prints out usage on incorrect invocation.
Recursive implementation for computing the Cartesian product of lists. In the pursuit of making it as interactive as possible, the parsing function ended up taking the most space. The product set expression must be supplied enclosed by double quotes. Prints out usage on incorrect invocation.
<syntaxhighlight lang=C>
<lang C>
#include<string.h>
#include<string.h>
#include<stdlib.h>
#include<stdlib.h>
Line 823: Line 823:
return 0;
return 0;
}
}
</syntaxhighlight>
</lang>
Invocation and output :
Invocation and output :
<pre>
<pre>
Line 850: Line 850:


=={{header|C sharp|C#}}==
=={{header|C sharp|C#}}==
<lang csharp>using System;
<syntaxhighlight lang=csharp>using System;
public class Program
public class Program
{
{
Line 893: Line 893:
select acc.Concat(new [] { item }));
select acc.Concat(new [] { item }));
}
}
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 904: Line 904:
{}</pre>
{}</pre>
If the number of lists is known, LINQ provides an easier solution:
If the number of lists is known, LINQ provides an easier solution:
<lang csharp>public static void Main()
<syntaxhighlight lang=csharp>public static void Main()
{
{
///...
///...
Line 919: Line 919:
select (a, b, c);
select (a, b, c);
Console.WriteLine($"{{{string.Join(", ", cart2)}}}");
Console.WriteLine($"{{{string.Join(", ", cart2)}}}");
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 927: Line 927:


=={{header|C++}}==
=={{header|C++}}==
<lang cpp>
<syntaxhighlight lang=cpp>
#include <iostream>
#include <iostream>
#include <vector>
#include <vector>
Line 983: Line 983:
std::cin.get();
std::cin.get();
return 0;
return 0;
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 995: Line 995:


=={{header|Clojure}}==
=={{header|Clojure}}==
<lang Clojure>
<syntaxhighlight lang=Clojure>
(ns clojure.examples.product
(ns clojure.examples.product
(:gen-class)
(:gen-class)
Line 1,007: Line 1,007:
x (first colls)]
x (first colls)]
(cons x more))))
(cons x more))))
</syntaxhighlight>
</lang>
'''Output'''
'''Output'''
<lang clojure>
<syntaxhighlight lang=clojure>
(doseq [lst [ [[1,2],[3,4]],
(doseq [lst [ [[1,2],[3,4]],
[[3,4],[1,2]], [[], [1, 2]],
[[3,4],[1,2]], [[], [1, 2]],
Line 1,020: Line 1,020:
(println lst "=>")
(println lst "=>")
(pp/pprint (cart lst)))
(pp/pprint (cart lst)))
</syntaxhighlight>
</lang>


<pre>
<pre>
Line 1,063: Line 1,063:


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
<lang lisp>(defun cartesian-product (s1 s2)
<syntaxhighlight lang=lisp>(defun cartesian-product (s1 s2)
"Compute the cartesian product of two sets represented as lists"
"Compute the cartesian product of two sets represented as lists"
(loop for x in s1
(loop for x in s1
nconc (loop for y in s2 collect (list x y))))
nconc (loop for y in s2 collect (list x y))))
</syntaxhighlight>
</lang>


'''Output'''
'''Output'''


<lang lisp>
<syntaxhighlight lang=lisp>
CL-USER> (cartesian-product '(1 2) '(3 4))
CL-USER> (cartesian-product '(1 2) '(3 4))
((1 3) (1 4) (2 3) (2 4))
((1 3) (1 4) (2 3) (2 4))
Line 1,080: Line 1,080:
CL-USER> (cartesian-product '() '(1 2))
CL-USER> (cartesian-product '() '(1 2))
NIL
NIL
</syntaxhighlight>
</lang>


'''Extra credit:'''
'''Extra credit:'''


<lang lisp>(defun n-cartesian-product (l)
<syntaxhighlight lang=lisp>(defun n-cartesian-product (l)
"Compute the n-cartesian product of a list of sets (each of them represented as list).
"Compute the n-cartesian product of a list of sets (each of them represented as list).
Algorithm:
Algorithm:
Line 1,094: Line 1,094:
(loop for x in (car l)
(loop for x in (car l)
nconc (loop for y in (n-cartesian-product (cdr l))
nconc (loop for y in (n-cartesian-product (cdr l))
collect (cons x y)))))</lang>
collect (cons x y)))))</syntaxhighlight>


'''Output:'''
'''Output:'''


<lang lisp>CL-USER> (n-cartesian-product '((1776 1789) (7 12) (4 14 23) (0 1)))
<syntaxhighlight lang=lisp>CL-USER> (n-cartesian-product '((1776 1789) (7 12) (4 14 23) (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))
((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))
CL-USER> (n-cartesian-product '((1 2 3) (30) (500 100)))
CL-USER> (n-cartesian-product '((1 2 3) (30) (500 100)))
Line 1,104: Line 1,104:
CL-USER> (n-cartesian-product '((1 2 3) () (500 100)))
CL-USER> (n-cartesian-product '((1 2 3) () (500 100)))
NIL
NIL
</syntaxhighlight>
</lang>


=={{header|Crystal}}==
=={{header|Crystal}}==
The first function is the basic task. The version overloaded for one argument is the extra credit task, implemented using recursion.
The first function is the basic task. The version overloaded for one argument is the extra credit task, implemented using recursion.
<lang crystal>def cartesian_product(a, b)
<syntaxhighlight lang=crystal>def cartesian_product(a, b)
return a.flat_map { |i| b.map { |j| [i, j] } }
return a.flat_map { |i| b.map { |j| [i, j] } }
end
end
Line 1,141: Line 1,141:
puts ""
puts ""
}
}
</syntaxhighlight>
</lang>


{{out}}
{{out}}
Line 1,167: Line 1,167:


=={{header|D}}==
=={{header|D}}==
<lang D>import std.stdio;
<syntaxhighlight lang=D>import std.stdio;


void main() {
void main() {
Line 1,205: Line 1,205:


return Result();
return Result();
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 1,215: Line 1,215:
{{libheader| System.SysUtils}}
{{libheader| System.SysUtils}}
{{Trans|Go}}
{{Trans|Go}}
<lang Delphi>
<syntaxhighlight lang=Delphi>
program Cartesian_product_of_two_or_more_lists;
program Cartesian_product_of_two_or_more_lists;


Line 1,324: Line 1,324:


{$IFNDEF UNIX} readln; {$ENDIF}
{$IFNDEF UNIX} readln; {$ENDIF}
end.</lang>
end.</syntaxhighlight>
{{out}}
{{out}}
<pre>[[1 3] [1 4] [2 3] [2 4]]
<pre>[[1 3] [1 4] [2 3] [2 4]]
Line 1,365: Line 1,365:
=={{header|F Sharp|F#}}==
=={{header|F Sharp|F#}}==
===The Task===
===The Task===
<lang fsharp>
<syntaxhighlight lang=fsharp>
//Nigel Galloway February 12th., 2018
//Nigel Galloway February 12th., 2018
let cP2 n g = List.map (fun (n,g)->[n;g]) (List.allPairs n g)
let cP2 n g = List.map (fun (n,g)->[n;g]) (List.allPairs n g)
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 1,378: Line 1,378:


===Extra Credit===
===Extra Credit===
<lang fsharp>
<syntaxhighlight lang=fsharp>
//Nigel Galloway August 14th., 2018
//Nigel Galloway August 14th., 2018
let cP ng=Seq.foldBack(fun n g->[for n' in n do for g' in g do yield n'::g']) ng [[]]
let cP ng=Seq.foldBack(fun n g->[for n' in n do for g' in g do yield n'::g']) ng [[]]
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 1,399: Line 1,399:


=={{header|Factor}}==
=={{header|Factor}}==
<lang Factor>IN: scratchpad { 1 2 } { 3 4 } cartesian-product .
<syntaxhighlight lang=Factor>IN: scratchpad { 1 2 } { 3 4 } cartesian-product .
{ { { 1 3 } { 1 4 } } { { 2 3 } { 2 4 } } }
{ { { 1 3 } { 1 4 } } { { 2 3 } { 2 4 } } }
IN: scratchpad { 3 4 } { 1 2 } cartesian-product .
IN: scratchpad { 3 4 } { 1 2 } cartesian-product .
Line 1,406: Line 1,406:
{ { } { } }
{ { } { } }
IN: scratchpad { } { 1 2 } cartesian-product .
IN: scratchpad { } { 1 2 } cartesian-product .
{ }</lang>
{ }</syntaxhighlight>


=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
I'll leave the extra credit part for someone else. It's just going to amount to repeatedly finding Cartesian products and [[Flatten a list|flattening]] the result, so considerably less interesting than Cartesian products where the list items themselves can be lists.
I'll leave the extra credit part for someone else. It's just going to amount to repeatedly finding Cartesian products and [[Flatten a list|flattening]] the result, so considerably less interesting than Cartesian products where the list items themselves can be lists.


<lang freebasic>#define MAXLEN 64
<syntaxhighlight lang=freebasic>#define MAXLEN 64


type listitem ' An item of a list may be a number
type listitem ' An item of a list may be a number
Line 1,472: Line 1,472:
R = cartprod(B, A) : print_list(R) : print
R = cartprod(B, A) : print_list(R) : print
R = cartprod(A, EMPTY) : print_list(R) : print
R = cartprod(A, EMPTY) : print_list(R) : print
R = cartprod(EMPTY, A) : print_list(R) : print</lang>
R = cartprod(EMPTY, A) : print_list(R) : print</syntaxhighlight>
{{out}}<pre>{{1, 3}, {1, 4}, {2, 3}, {2, 4}}
{{out}}<pre>{{1, 3}, {1, 4}, {2, 3}, {2, 4}}
{{3, 1}, {3, 2}, {4, 1}, {4, 2}}
{{3, 1}, {3, 2}, {4, 1}, {4, 2}}
Line 1,482: Line 1,482:
This implementation is hard to extend to n-ary products but it is simple and works well for binary products of lists of any length.
This implementation is hard to extend to n-ary products but it is simple and works well for binary products of lists of any length.


<lang fortran>
<syntaxhighlight lang=fortran>
! Created by simon on 29/04/2021.
! Created by simon on 29/04/2021.
Line 1,581: Line 1,581:
end subroutine print_product
end subroutine print_product
end program cartesian_product
end program cartesian_product
</syntaxhighlight>
</lang>
'''Output:'''
'''Output:'''
{1,2} x {3,4} = {{1,3},{1,4},{2,3},{2,4}}
{1,2} x {3,4} = {{1,3},{1,4},{2,3},{2,4}}
Line 1,600: Line 1,600:
=={{header|Go}}==
=={{header|Go}}==
'''Basic Task'''
'''Basic Task'''
<lang go>package main
<syntaxhighlight lang=go>package main


import "fmt"
import "fmt"
Line 1,623: Line 1,623:
fmt.Println(cart2([]int{1, 2}, nil))
fmt.Println(cart2([]int{1, 2}, nil))
fmt.Println(cart2(nil, []int{1, 2}))
fmt.Println(cart2(nil, []int{1, 2}))
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,634: Line 1,634:


This solution minimizes allocations and computes and fills the result sequentially.
This solution minimizes allocations and computes and fills the result sequentially.
<lang go>package main
<syntaxhighlight lang=go>package main


import "fmt"
import "fmt"
Line 1,692: Line 1,692:
fmt.Println(cartN(nil))
fmt.Println(cartN(nil))
fmt.Println(cartN())
fmt.Println(cartN())
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,735: Line 1,735:


Code here is more compact, but with the cost of more garbage produced. It produces the same result as cartN above.
Code here is more compact, but with the cost of more garbage produced. It produces the same result as cartN above.
<lang go>func cartN(a ...[]int) (c [][]int) {
<syntaxhighlight lang=go>func cartN(a ...[]int) (c [][]int) {
if len(a) == 0 {
if len(a) == 0 {
return [][]int{nil}
return [][]int{nil}
Line 1,746: Line 1,746:
}
}
return
return
}</lang>
}</syntaxhighlight>
'''Extra credit 3'''
'''Extra credit 3'''


This is a compact recursive version like Extra credit 2 but the result list is ordered differently. This is still a correct result if you consider a cartesian product to be a set, which is an unordered collection. Note that the set elements are still ordered lists. A cartesian product is an unordered collection of ordered collections. It draws attention though to the gloss of using list representations as sets. Any of the functions here will accept duplicate elements in the input lists, and then produce duplicate elements in the result.
This is a compact recursive version like Extra credit 2 but the result list is ordered differently. This is still a correct result if you consider a cartesian product to be a set, which is an unordered collection. Note that the set elements are still ordered lists. A cartesian product is an unordered collection of ordered collections. It draws attention though to the gloss of using list representations as sets. Any of the functions here will accept duplicate elements in the input lists, and then produce duplicate elements in the result.
<lang go>func cartN(a ...[]int) (c [][]int) {
<syntaxhighlight lang=go>func cartN(a ...[]int) (c [][]int) {
if len(a) == 0 {
if len(a) == 0 {
return [][]int{nil}
return [][]int{nil}
Line 1,762: Line 1,762:
}
}
return
return
}</lang>
}</syntaxhighlight>


=={{header|Groovy}}==
=={{header|Groovy}}==
'''Solution:'''<br>
'''Solution:'''<br>
The following ''CartesianCategory'' class allows for modification of regular ''Iterable'' interface behavior, overloading ''Iterable'''s ''multiply'' (*) operator to perform a Cartesian Product when the second operand is also an ''Iterable''.
The following ''CartesianCategory'' class allows for modification of regular ''Iterable'' interface behavior, overloading ''Iterable'''s ''multiply'' (*) operator to perform a Cartesian Product when the second operand is also an ''Iterable''.
<lang groovy>class CartesianCategory {
<syntaxhighlight lang=groovy>class CartesianCategory {
static Iterable multiply(Iterable a, Iterable b) {
static Iterable multiply(Iterable a, Iterable b) {
assert [a,b].every { it != null }
assert [a,b].every { it != null }
Line 1,773: Line 1,773:
(0..<(m*n)).inject([]) { prod, i -> prod << [a[i.intdiv(n)], b[i%n]].flatten() }
(0..<(m*n)).inject([]) { prod, i -> prod << [a[i.intdiv(n)], b[i%n]].flatten() }
}
}
}</lang>
}</syntaxhighlight>
'''Test:'''<br>
'''Test:'''<br>
The ''mixin'' method call is necessary to make the multiply (*) operator work.
The ''mixin'' method call is necessary to make the multiply (*) operator work.
<lang groovy>Iterable.metaClass.mixin CartesianCategory
<syntaxhighlight lang=groovy>Iterable.metaClass.mixin CartesianCategory


println "\nCore Solution:"
println "\nCore Solution:"
Line 1,792: Line 1,792:
println "[John,Paul,George,Ringo] × [Emerson,Lake,Palmer] × [Simon,Garfunkle] = ["
println "[John,Paul,George,Ringo] × [Emerson,Lake,Palmer] × [Simon,Garfunkle] = ["
( ["John","Paul","George","Ringo"] * ["Emerson","Lake","Palmer"] * ["Simon","Garfunkle"] ).each { println "\t${it}," }
( ["John","Paul","George","Ringo"] * ["Emerson","Lake","Palmer"] * ["Simon","Garfunkle"] ).each { println "\t${it}," }
println "]"</lang>
println "]"</syntaxhighlight>
'''Output:'''
'''Output:'''
<pre>
<pre>
Line 1,837: Line 1,837:
Various routes can be taken to Cartesian products in Haskell.
Various routes can be taken to Cartesian products in Haskell.
For the product of two lists we could write:
For the product of two lists we could write:
<lang Haskell>cartProd :: [a] -> [b] -> [(a, b)]
<syntaxhighlight lang=Haskell>cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys =
cartProd xs ys =
[ (x, y)
[ (x, y)
| x <- xs
| x <- xs
, y <- ys ]</lang>
, y <- ys ]</syntaxhighlight>


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


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


parsimoniously:
parsimoniously:
<lang Haskell>cartProd :: [a] -> [b] -> [(a, b)]
<syntaxhighlight lang=Haskell>cartProd :: [a] -> [b] -> [(a, b)]
cartProd = (<*>) . fmap (,)</lang>
cartProd = (<*>) . fmap (,)</syntaxhighlight>


We might test any of these with:
We might test any of these with:
<lang haskell>main :: IO ()
<syntaxhighlight lang=haskell>main :: IO ()
main =
main =
mapM_ print $
mapM_ print $
uncurry cartProd <$>
uncurry cartProd <$>
[([1, 2], [3, 4]), ([3, 4], [1, 2]), ([1, 2], []), ([], [1, 2])]</lang>
[([1, 2], [3, 4]), ([3, 4], [1, 2]), ([1, 2], []), ([], [1, 2])]</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[(1,3),(1,4),(2,3),(2,4)]
<pre>[(1,3),(1,4),(2,3),(2,4)]
Line 1,869: Line 1,869:


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,
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]]
<syntaxhighlight lang=haskell>cartProdN :: [[a]] -> [[a]]
cartProdN = sequence
cartProdN = sequence


main :: IO ()
main :: IO ()
main = print $ cartProdN [[1, 2], [3, 4], [5, 6]]</lang>
main = print $ cartProdN [[1, 2], [3, 4], [5, 6]]</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]</pre>
<pre>[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]</pre>


or we could define ourselves an equivalent function over a list of lists in terms of a fold, for example as:
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]]
<syntaxhighlight lang=haskell>cartProdN :: [[a]] -> [[a]]
cartProdN = foldr (\xs as -> xs >>= (<$> as) . (:)) [[]]</lang>
cartProdN = foldr (\xs as -> xs >>= (<$> as) . (:)) [[]]</syntaxhighlight>
or, equivalently, as:
or, equivalently, as:
<lang haskell>cartProdN :: [[a]] -> [[a]]
<syntaxhighlight lang=haskell>cartProdN :: [[a]] -> [[a]]
cartProdN = foldr
cartProdN = foldr
(\xs as ->
(\xs as ->
Line 1,887: Line 1,887:
| x <- xs
| x <- xs
, a <- as ])
, a <- as ])
[[]]</lang>
[[]]</syntaxhighlight>
testing any of these with something like:
testing any of these with something like:
<lang haskell>main :: IO ()
<syntaxhighlight lang=haskell>main :: IO ()
main = do
main = do
mapM_ print $
mapM_ print $
Line 1,896: Line 1,896:
print $ cartProdN [[1,2,3], [30], [500, 100]]
print $ cartProdN [[1,2,3], [30], [500, 100]]
putStrLn ""
putStrLn ""
print $ cartProdN [[1,2,3], [], [500, 100]]</lang>
print $ cartProdN [[1,2,3], [], [500, 100]]</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[1776,7,4,0]
<pre>[1776,7,4,0]
Line 1,929: Line 1,929:
=={{header|J}}==
=={{header|J}}==
The J primitive [http://code.jsoftware.com/wiki/Vocabulary/curlylf catalogue] <code>{</code> 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).
The J primitive [http://code.jsoftware.com/wiki/Vocabulary/curlylf catalogue] <code>{</code> 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
<syntaxhighlight 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 4 0 │1776 7 4 1 │
Line 1,971: Line 1,971:
└───────┴────────┘
└───────┴────────┘
{ 1 2 3 ; '' ; 50 100 NB. result is an empty 3-dimensional array with shape 3 0 2
{ 1 2 3 ; '' ; 50 100 NB. result is an empty 3-dimensional array with shape 3 0 2
</syntaxhighlight>
</lang>


=={{header|Java}}==
=={{header|Java}}==
{{works with|Java Virtual Machine|1.8}}
{{works with|Java Virtual Machine|1.8}}
<lang Java>
<syntaxhighlight lang=Java>
import static java.util.Arrays.asList;
import static java.util.Arrays.asList;
import static java.util.Collections.emptyList;
import static java.util.Collections.emptyList;
Line 2,004: Line 2,004:
}
}
}
}
</syntaxhighlight>
</lang>


'''Using a generic class with a recursive function'''
'''Using a generic class with a recursive function'''
<lang Java>
<syntaxhighlight lang=Java>
import java.util.ArrayList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Arrays;
Line 2,063: Line 2,063:
}
}
}
}
</syntaxhighlight>
</lang>


=={{header|JavaScript}}==
=={{header|JavaScript}}==
Line 2,071: Line 2,071:


For the Cartesian product of just two lists:
For the Cartesian product of just two lists:
<lang JavaScript>(() => {
<syntaxhighlight lang=JavaScript>(() => {
// CARTESIAN PRODUCT OF TWO LISTS ---------------------
// CARTESIAN PRODUCT OF TWO LISTS ---------------------


Line 2,086: Line 2,086:
cartProd([])([1, 2]),
cartProd([])([1, 2]),
].map(JSON.stringify).join('\n');
].map(JSON.stringify).join('\n');
})();</lang>
})();</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[[1,3],[1,4],[2,3],[2,4]]
<pre>[[1,3],[1,4],[2,3],[2,4]]
Line 2,095: Line 2,095:


Abstracting a little more, we can define the cartesian product quite economically in terms of a general applicative operator:
Abstracting a little more, we can define the cartesian product quite economically in terms of a general applicative operator:
<lang Javascript>(() => {
<syntaxhighlight lang=Javascript>(() => {


// CARTESIAN PRODUCT OF TWO LISTS ---------------------
// CARTESIAN PRODUCT OF TWO LISTS ---------------------
Line 2,133: Line 2,133:
.map(JSON.stringify)
.map(JSON.stringify)
.join('\n');
.join('\n');
})();</lang>
})();</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[[1,3],[1,4],[2,3],[2,4]]
<pre>[[1,3],[1,4],[2,3],[2,4]]
Line 2,141: Line 2,141:


For the n-ary Cartesian product over a list of lists:
For the n-ary Cartesian product over a list of lists:
<lang JavaScript>(() => {
<syntaxhighlight lang=JavaScript>(() => {
const main = () => {
const main = () => {
// n-ary Cartesian product of a list of lists.
// n-ary Cartesian product of a list of lists.
Line 2,201: Line 2,201:


return main();
return main();
})();</lang>
})();</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[1776,7,4,0]
<pre>[1776,7,4,0]
Line 2,235: Line 2,235:
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''':
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>(() => {
<syntaxhighlight lang=JavaScript>(() => {
// n-ary Cartesian product of a list of lists
// n-ary Cartesian product of a list of lists
// ( Imperative implementation )
// ( Imperative implementation )
Line 2,308: Line 2,308:
]))
]))
]);
]);
})();</lang>
})();</syntaxhighlight>
{{Out}}
{{Out}}
<pre>[[1,4],[1,3],[2,4],[2,3]]
<pre>[[1,4],[1,3],[2,4],[2,3]]
Line 2,350: Line 2,350:


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:
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:
<syntaxhighlight lang=jq>
<lang jq>
def products: .[0][] as $x | .[1][] as $y | [$x,$y];
def products: .[0][] as $x | .[1][] as $y | [$x,$y];
</syntaxhighlight>
</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:
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:
<syntaxhighlight lang=jq>
<lang jq>
def product: [products];
def product: [products];
</syntaxhighlight>
</lang>


For the sake of brevity, two illustrations should suffice:
For the sake of brevity, two illustrations should suffice:
Line 2,372: Line 2,372:


And
And
<syntaxhighlight lang=jq>
<lang jq>
[[1,2], []] | product
[[1,2], []] | product
</syntaxhighlight>
</lang>
produces:
produces:
<pre>
<pre>
Line 2,383: Line 2,383:
Given an array of two or more arrays as input, `cartesians` as defined here produces a stream of the components of their 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:


<syntaxhighlight lang=jq>
<lang jq>
def cartesians:
def cartesians:
if length <= 2 then products
if length <= 2 then products
Line 2,390: Line 2,390:
| [$x] + $y
| [$x] + $y
end;
end;
</syntaxhighlight>
</lang>


Again for brevity, in the following, we will just show the number of items in the Cartesian products:
Again for brevity, in the following, we will just show the number of items in the Cartesian products:
Line 2,405: Line 2,405:
=={{header|Julia}}==
=={{header|Julia}}==
Run in REPL.
Run in REPL.
<lang julia>
<syntaxhighlight lang=julia>
# Product {1, 2} × {3, 4}
# Product {1, 2} × {3, 4}
collect(Iterators.product([1, 2], [3, 4]))
collect(Iterators.product([1, 2], [3, 4]))
Line 2,422: Line 2,422:
# Product {1, 2, 3} × {} × {500, 100}
# Product {1, 2, 3} × {} × {500, 100}
collect(Iterators.product([1, 2, 3], [], [500, 100]))
collect(Iterators.product([1, 2, 3], [], [500, 100]))
</syntaxhighlight>
</lang>


=={{header|Kotlin}}==
=={{header|Kotlin}}==
<lang scala>// version 1.1.2
<syntaxhighlight lang=scala>// version 1.1.2


fun flattenList(nestList: List<Any>): List<Any> {
fun flattenList(nestList: List<Any>): List<Any> {
Line 2,477: Line 2,477:
printNAryProduct(listOf(listOf(1, 2, 3), listOf<Int>(), 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')))
printNAryProduct(listOf(listOf(1, 2, 3), listOf(30), listOf('a', 'b')))
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 2,545: Line 2,545:


{{works with|langur|0.8.3}}
{{works with|langur|0.8.3}}
<lang langur>writeln X([1, 2], [3, 4]) == [[1, 3], [1, 4], [2, 3], [2, 4]]
<syntaxhighlight lang=langur>writeln X([1, 2], [3, 4]) == [[1, 3], [1, 4], [2, 3], [2, 4]]
writeln X([3, 4], [1, 2]) == [[3, 1], [3, 2], [4, 1], [4, 2]]
writeln X([3, 4], [1, 2]) == [[3, 1], [3, 2], [4, 1], [4, 2]]
writeln X([1, 2], []) == []
writeln X([1, 2], []) == []
Line 2,558: Line 2,558:


writeln X [1, 2, 3], [], [500, 100]
writeln X [1, 2, 3], [], [500, 100]
writeln()</lang>
writeln()</syntaxhighlight>


{{out}}
{{out}}
Line 2,576: Line 2,576:
=== Functional ===
=== Functional ===
An iterator is created to output the product items.
An iterator is created to output the product items.
<lang lua> local pk,upk = table.pack, table.unpack
<syntaxhighlight lang=lua> local pk,upk = table.pack, table.unpack
local getn = function(t)return #t end
local getn = function(t)return #t end
local const = function(k)return function(e) return k end end
local const = function(k)return function(e) return k end end
Line 2,625: Line 2,625:
print(i,a,b)
print(i,a,b)
end
end
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>1 1 3
<pre>1 1 3
Line 2,641: Line 2,641:


It is possible that specialising descend by depth may yield a further improvement in performance, but it would only be able to eliminate the lookup of ''sets[depth]'' and the if test, because the reference to ''result[depth]'' is required; I doubt the increase in complexity would be worth the (potential) improvement in performance.
It is possible that specialising descend by depth may yield a further improvement in performance, but it would only be able to eliminate the lookup of ''sets[depth]'' and the if test, because the reference to ''result[depth]'' is required; I doubt the increase in complexity would be worth the (potential) improvement in performance.
<lang lua>local function cartesian_product(sets)
<syntaxhighlight lang=lua>local function cartesian_product(sets)
local result = {}
local result = {}
local set_count = #sets
local set_count = #sets
Line 2,689: Line 2,689:
print(" " .. format_nested_list(product))
print(" " .. format_nested_list(product))
end
end
end</lang>
end</syntaxhighlight>


=== Imperative iterator ===
=== Imperative iterator ===
The functional implementation restated as an imperative iterator, also adjusted to not allocate a new result table on each iteration; this saves time, but makes mutating the returned table unsafe.
The functional implementation restated as an imperative iterator, also adjusted to not allocate a new result table on each iteration; this saves time, but makes mutating the returned table unsafe.
<lang lua>local function cartesian_product(sets)
<syntaxhighlight lang=lua>local function cartesian_product(sets)
local item_counts = {}
local item_counts = {}
local indices = {}
local indices = {}
Line 2,766: Line 2,766:
print(i, format_nested_list(product))
print(i, format_nested_list(product))
end
end
end</lang>
end</syntaxhighlight>


=== Functional-esque (non-iterator) ===
=== 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.
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:
<syntaxhighlight lang=lua>-- support:
function T(t) return setmetatable(t, {__index=table}) end
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.clone = function(t) local s=T{} for k,v in ipairs(t) do s[k]=v end return s end
Line 2,801: Line 2,801:
local cp = cartprod(test)
local cp = cartprod(test)
print("{"..cp:reduce(function(t,a) return (a=="" and a or a..", ").."("..t:concat(", ")..")" end,"").."}")
print("{"..cp:reduce(function(t,a) return (a=="" and a or a..", ").."("..t:concat(", ")..")" end,"").."}")
end</lang>
end</syntaxhighlight>
{{out}}
{{out}}
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}
Line 2,812: Line 2,812:


=={{header|Maple}}==
=={{header|Maple}}==
<lang Maple>
<syntaxhighlight lang=Maple>
cartmulti := proc ()
cartmulti := proc ()
local m, v;
local m, v;
Line 2,824: Line 2,824:
end if;
end if;
end proc;
end proc;
</syntaxhighlight>
</lang>


=={{header|Mathematica}}/{{header|Wolfram Language}}==
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<lang Mathematica>cartesianProduct[args__] := Flatten[Outer[List, args], Length[{args}] - 1]</lang>
<syntaxhighlight lang=Mathematica>cartesianProduct[args__] := Flatten[Outer[List, args], Length[{args}] - 1]</syntaxhighlight>


=={{header|Modula-2}}==
=={{header|Modula-2}}==
<lang modula2>MODULE CartesianProduct;
<syntaxhighlight lang=modula2>MODULE CartesianProduct;
FROM FormatString IMPORT FormatString;
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 2,878: Line 2,878:


ReadChar
ReadChar
END CartesianProduct.</lang>
END CartesianProduct.</syntaxhighlight>


=={{header|Nim}}==
=={{header|Nim}}==
Line 2,888: Line 2,888:
In order to display the result using mathematical formalism, we have created a special procedure “$$” for the sequences and have overloaded the procedure “$” for tuples.
In order to display the result using mathematical formalism, we have created a special procedure “$$” for the sequences and have overloaded the procedure “$” for tuples.


<lang Nim>iterator product[T1, T2](a: openArray[T1]; b: openArray[T2]): tuple[a: T1, b: T2] =
<syntaxhighlight lang=Nim>iterator product[T1, T2](a: openArray[T1]; b: openArray[T2]): tuple[a: T1, b: T2] =
# Yield the element of the cartesian product of "a" and "b".
# Yield the element of the cartesian product of "a" and "b".
# Yield tuples rather than arrays as it allows T1 and T2 to be different.
# Yield tuples rather than arrays as it allows T1 and T2 to be different.
Line 2,927: Line 2,927:
( Empty, @[1, 2])]:
( Empty, @[1, 2])]:


echo &"{$$a} x {$$b} = {$$toSeq(product(a, b))}"</lang>
echo &"{$$a} x {$$b} = {$$toSeq(product(a, b))}"</syntaxhighlight>


{{out}}
{{out}}
Line 2,942: Line 2,942:
Note that there exists in the standard module “algorithm” a procedure which computes the product of sequences of a same type. It is not recursive and, so, likely more efficient that the following version.
Note that there exists in the standard module “algorithm” a procedure which computes the product of sequences of a same type. It is not recursive and, so, likely more efficient that the following version.


<lang Nim>proc product[T](a: varargs[seq[T]]): seq[seq[T]] =
<syntaxhighlight lang=Nim>proc product[T](a: varargs[seq[T]]): seq[seq[T]] =
## Return the product of several sets (sequences).
## Return the product of several sets (sequences).


Line 2,963: Line 2,963:
b = @[3, 4]
b = @[3, 4]
c = @[5, 6]
c = @[5, 6]
echo &"{a} x {b} x {c} = {product(a, b, c)}"</lang>
echo &"{a} x {b} x {c} = {product(a, b, c)}"</syntaxhighlight>


{{out}}
{{out}}
Line 2,973: Line 2,973:
With a macro, we are able to mix several value types: the “varrags” is no longer a problem as being used at compile time it may contain sequences of different types. And we are able to return tuples of n values instead of sequences of n values.
With a macro, we are able to mix several value types: the “varrags” is no longer a problem as being used at compile time it may contain sequences of different types. And we are able to return tuples of n values instead of sequences of n values.


<lang Nim>import macros
<syntaxhighlight lang=Nim>import macros


macro product(args: varargs[typed]): untyped =
macro product(args: varargs[typed]): untyped =
Line 3,046: Line 3,046:
var b = @['a', 'b']
var b = @['a', 'b']
var c = @[false, true]
var c = @[false, true]
echo &"{$$a} x {$$b} x {$$c} = {$$product(a, b, c)}"</lang>
echo &"{$$a} x {$$b} x {$$c} = {$$product(a, b, c)}"</syntaxhighlight>


{{out}}
{{out}}
Line 3,054: Line 3,054:
''The double semicolons are necessary only for the toplevel''
''The double semicolons are necessary only for the toplevel''


Naive but more readable version<lang ocaml>let rec product l1 l2 =
Naive but more readable version<syntaxhighlight lang=ocaml>let rec product l1 l2 =
match l1, l2 with
match l1, l2 with
| [], _ | _, [] -> []
| [], _ | _, [] -> []
Line 3,067: Line 3,067:
(*- : (int * 'a) list = []*)
(*- : (int * 'a) list = []*)
product [] [1;2];;
product [] [1;2];;
(*- : ('a * int) list = []*)</lang>
(*- : ('a * int) list = []*)</syntaxhighlight>


Implementation with a bit more tail-call optimization, introducing a helper function. The order of the result is changed but it should not be an issue for most uses.
Implementation with a bit more tail-call optimization, introducing a helper function. The order of the result is changed but it should not be an issue for most uses.
<lang ocaml>let product' l1 l2 =
<syntaxhighlight lang=ocaml>let product' l1 l2 =
let rec aux ~acc l1' l2' =
let rec aux ~acc l1' l2' =
match l1', l2' with
match l1', l2' with
Line 3,088: Line 3,088:
(*- : (int * 'a) list = []*)
(*- : (int * 'a) list = []*)
product' [] [1;2];;
product' [] [1;2];;
(*- : ('a * int) list = []*)</lang>
(*- : ('a * int) list = []*)</syntaxhighlight>
Implemented using nested folds:
Implemented using nested folds:
<lang ocaml>let cart_prod l1 l2 =
<syntaxhighlight lang=ocaml>let cart_prod l1 l2 =
List.fold_left (fun acc1 ele1 ->
List.fold_left (fun acc1 ele1 ->
List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;;
List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;;
Line 3,097: Line 3,097:
(*- : (int * char) list = [(3, 'c'); (3, 'b'); (3, 'a'); (2, 'c'); (2, 'b'); (2, 'a'); (1, 'c'); (1, 'b'); (1, 'a')]*)
(*- : (int * char) list = [(3, 'c'); (3, 'b'); (3, 'a'); (2, 'c'); (2, 'b'); (2, 'a'); (1, 'c'); (1, 'b'); (1, 'a')]*)
cart_prod [1; 2; 3] [] ;;
cart_prod [1; 2; 3] [] ;;
(*- : ('a * int) list = [] *)</lang>
(*- : ('a * int) list = [] *)</syntaxhighlight>


Extra credit function. Since in OCaml a function can return only one type, and because tuples of different arities are different types, this returns a list of lists rather than a list of tuples. Since lists are homogeneous this version is restricted to products over a ''single'' type, eg integers.
Extra credit function. Since in OCaml a function can return only one type, and because tuples of different arities are different types, this returns a list of lists rather than a list of tuples. Since lists are homogeneous this version is restricted to products over a ''single'' type, eg integers.
<lang ocaml>let rec product'' l =
<syntaxhighlight lang=ocaml>let rec product'' l =
(* We need to do the cross product of our current list and all the others
(* We need to do the cross product of our current list and all the others
* so we define a helper function for that *)
* so we define a helper function for that *)
Line 3,145: Line 3,145:
*)
*)
product'' [[1; 2; 3];[];[500; 100]];;
product'' [[1; 2; 3];[];[500; 100]];;
(*- : int list list = []*)</lang>
(*- : int list list = []*)</syntaxhighlight>


=== Better type ===
=== Better type ===


In the latter example, our function has this signature:
In the latter example, our function has this signature:
<lang ocaml>val product'' : 'a list list -> 'a list list = <fun></lang>
<syntaxhighlight lang=ocaml>val product'' : 'a list list -> 'a list list = <fun></syntaxhighlight>
This lacks clarity as those two lists are not equivalent since one replaces a tuple. We can get a better signature by creating a tuple type:
This lacks clarity as those two lists are not equivalent since one replaces a tuple. We can get a better signature by creating a tuple type:
<lang ocaml>type 'a tuple = 'a list
<syntaxhighlight lang=ocaml>type 'a tuple = 'a list


let rec product'' (l:'a list tuple) =
let rec product'' (l:'a list tuple) =
Line 3,173: Line 3,173:


type 'a tuple = 'a list
type 'a tuple = 'a list
val product'' : 'a list tuple -> 'a tuple list = <fun></lang>
val product'' : 'a list tuple -> 'a tuple list = <fun></syntaxhighlight>


=={{header|Perl}}==
=={{header|Perl}}==
==== Iterative ====
==== Iterative ====
Nested loops, with a short-circuit to quit early if any term is an empty set.
Nested loops, with a short-circuit to quit early if any term is an empty set.
<lang perl>sub cartesian {
<syntaxhighlight lang=perl>sub cartesian {
my $sets = shift @_;
my $sets = shift @_;
for (@$sets) { return [] unless @$_ }
for (@$sets) { return [] unless @$_ }
Line 3,209: Line 3,209:
product([[1,2,3], [30], [500,100] ], '%1d %1d %3d' ).
product([[1,2,3], [30], [500,100] ], '%1d %1d %3d' ).
product([[1,2,3], [], [500,100] ], '%1d %1d %3d' ).
product([[1,2,3], [], [500,100] ], '%1d %1d %3d' ).
product([[1776,1789], [7,12], [4,14,23], [0,1]], '%4d %2d %2d %1d')</lang>
product([[1776,1789], [7,12], [4,14,23], [0,1]], '%4d %2d %2d %1d')</syntaxhighlight>
{{out}}
{{out}}
<pre>(1 3) (1 4) (2 3) (2 4)
<pre>(1 3) (1 4) (2 3) (2 4)
Line 3,221: Line 3,221:
==== Glob ====
==== Glob ====
This being Perl, there's more than one way to do it. A quick demonstration of how <code>glob</code>, more typically used for filename wildcard expansion, can solve the task.
This being Perl, there's more than one way to do it. A quick demonstration of how <code>glob</code>, more typically used for filename wildcard expansion, can solve the task.
<lang perl>$tuples = [ map { [split /:/] } glob '{1,2,3}:{30}:{500,100}' ];
<syntaxhighlight lang=perl>$tuples = [ map { [split /:/] } glob '{1,2,3}:{30}:{500,100}' ];


for $a (@$tuples) { printf "(%1d %2d %3d) ", @$a; }</lang>
for $a (@$tuples) { printf "(%1d %2d %3d) ", @$a; }</syntaxhighlight>
{{out}}
{{out}}
<pre>(1 30 500) (1 30 100) (2 30 500) (2 30 100) (3 30 500) (3 30 100)</pre>
<pre>(1 30 500) (1 30 100) (2 30 500) (2 30 100) (3 30 500) (3 30 100)</pre>
Line 3,229: Line 3,229:
==== Modules ====
==== Modules ====
A variety of modules can do this correctly for an arbitrary number of lists (each of independent length). Arguably using modules is very idiomatic Perl.
A variety of modules can do this correctly for an arbitrary number of lists (each of independent length). Arguably using modules is very idiomatic Perl.
<lang perl>use ntheory qw/forsetproduct/;
<syntaxhighlight lang=perl>use ntheory qw/forsetproduct/;
forsetproduct { say "@_" } [1,2,3],[qw/a b c/],[qw/@ $ !/];
forsetproduct { say "@_" } [1,2,3],[qw/a b c/],[qw/@ $ !/];


Line 3,239: Line 3,239:


use Algorithm::Loops qw/NestedLoops/;
use Algorithm::Loops qw/NestedLoops/;
NestedLoops([[1,2,3],[qw/a b c/],[qw/@ $ !/]], sub { say "@_"; });</lang>
NestedLoops([[1,2,3],[qw/a b c/],[qw/@ $ !/]], sub { say "@_"; });</syntaxhighlight>


=={{header|Phix}}==
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
<!--<syntaxhighlight lang=Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cart</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cart</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
Line 3,266: Line 3,266:
<span style="color: #0000FF;">?</span><span style="color: #000000;">cart</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">}})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">cart</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">}})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">cart</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},{},{</span><span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">}})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">cart</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},{},{</span><span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">}})</span>
<!--</lang>-->
<!--</syntaxhighlight>-->
{{out}}
{{out}}
<pre>
<pre>
Line 3,282: Line 3,282:


=={{header|Phixmonti}}==
=={{header|Phixmonti}}==
<lang Phixmonti>include ..\Utilitys.pmt
<syntaxhighlight lang=Phixmonti>include ..\Utilitys.pmt


def cart
def cart
Line 3,312: Line 3,312:


( ( 1 2 ) ( ) ) cart
( ( 1 2 ) ( ) ) cart
drop res print nl nl</lang>
drop res print nl nl</syntaxhighlight>


=={{header|PicoLisp}}==
=={{header|PicoLisp}}==
<lang PicoLisp>(de 2lists (L1 L2)
<syntaxhighlight lang=PicoLisp>(de 2lists (L1 L2)
(mapcan
(mapcan
'((I)
'((I)
Line 3,340: Line 3,340:
(cartesian (1 2 3) (30) (500 100)) )
(cartesian (1 2 3) (30) (500 100)) )
(println
(println
(cartesian (1 2 3) NIL (500 100)) )</lang>
(cartesian (1 2 3) NIL (500 100)) )</syntaxhighlight>


{{out}}
{{out}}
Line 3,352: Line 3,352:


=={{header|Prolog}}==
=={{header|Prolog}}==
<lang Prolog>
<syntaxhighlight lang=Prolog>
product([A|_], Bs, [A, B]) :- member(B, Bs).
product([A|_], Bs, [A, B]) :- member(B, Bs).
product([_|As], Bs, X) :- product(As, Bs, X).
product([_|As], Bs, X) :- product(As, Bs, X).
</syntaxhighlight>
</lang>
{{Out}}
{{Out}}
<pre>
<pre>
Line 3,372: Line 3,372:
=={{header|Python}}==
=={{header|Python}}==
===Using itertools===
===Using itertools===
<lang python>import itertools
<syntaxhighlight lang=python>import itertools


def cp(lsts):
def cp(lsts):
Line 3,386: Line 3,386:
print(lists, '=>')
print(lists, '=>')
pp(cp(lists), indent=2)
pp(cp(lists), indent=2)
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>[[1, 2], [3, 4]] =>
<pre>[[1, 2], [3, 4]] =>
Line 3,437: Line 3,437:
If we write ourselves a re-usable Python '''ap''' function for the case of lists (applicative functions for other 'data containers' can also be written – this one applies a list of functions to a list of values):
If we write ourselves a re-usable Python '''ap''' function for the case of lists (applicative functions for other 'data containers' can also be written – this one applies a list of functions to a list of values):


<lang python># ap (<*>) :: [(a -> b)] -> [a] -> [b]
<syntaxhighlight lang=python># ap (<*>) :: [(a -> b)] -> [a] -> [b]
def ap(fs):
def ap(fs):
return lambda xs: foldl(
return lambda xs: foldl(
lambda a: lambda f: a + foldl(
lambda a: lambda f: a + foldl(
lambda a: lambda x: a + [f(x)])([])(xs)
lambda a: lambda x: a + [f(x)])([])(xs)
)([])(fs)</lang>
)([])(fs)</syntaxhighlight>


then one simple use of it will be to define the cartesian product of two lists (of possibly different type) as:
then one simple use of it will be to define the cartesian product of two lists (of possibly different type) as:


<lang python>ap(map(Tuple, xs))</lang>
<syntaxhighlight lang=python>ap(map(Tuple, xs))</syntaxhighlight>


where Tuple is a constructor, and xs is bound to the first of two lists. The returned value is a function which can be applied to a second list.
where Tuple is a constructor, and xs is bound to the first of two lists. The returned value is a function which can be applied to a second list.
Line 3,452: Line 3,452:
For an nAry product, we can then use a '''fold''' (catamorphism) to lift the basic function over two lists ''cartesianProduct :: [a] -> [b] -> [(a, b)]'' to a function over a list of lists:
For an nAry product, we can then use a '''fold''' (catamorphism) to lift the basic function over two lists ''cartesianProduct :: [a] -> [b] -> [(a, b)]'' to a function over a list of lists:


<lang python># nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]
<syntaxhighlight lang=python># nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]
def nAryCartProd(xxs):
def nAryCartProd(xxs):
return foldl1(cartesianProduct)(
return foldl1(cartesianProduct)(
xxs
xxs
)</lang>
)</syntaxhighlight>


For example:
For example:


<lang python># Two lists -> list of tuples
<syntaxhighlight lang=python># Two lists -> list of tuples




Line 3,567: Line 3,567:
# TEST ----------------------------------------------------
# TEST ----------------------------------------------------
if __name__ == '__main__':
if __name__ == '__main__':
main()</lang>
main()</syntaxhighlight>
{{Out}}
{{Out}}
<pre>Product of two lists of different types:
<pre>Product of two lists of different types:
Line 3,606: Line 3,606:
=={{header|Quackery}}==
=={{header|Quackery}}==


<lang Quackery> [ [] unrot
<syntaxhighlight lang=Quackery> [ [] unrot
swap witheach
swap witheach
[ over witheach
[ over witheach
Line 3,618: Line 3,618:
' [ 3 4 ] ' [ 1 2 ] cartprod echo cr
' [ 3 4 ] ' [ 1 2 ] cartprod echo cr
' [ 1 2 ] ' [ ] cartprod echo cr
' [ 1 2 ] ' [ ] cartprod echo cr
' [ ] ' [ 1 2 ] cartprod echo cr</lang>
' [ ] ' [ 1 2 ] cartprod echo cr</syntaxhighlight>


{{out}}
{{out}}
Line 3,630: Line 3,630:
=={{header|R}}==
=={{header|R}}==


<syntaxhighlight lang=R>
<lang R>
one_w_many <- function(one, many) lapply(many, function(x) c(one,x))
one_w_many <- function(one, many) lapply(many, function(x) c(one,x))


Line 3,648: Line 3,648:
prod = Reduce( '%p%', list(...) )
prod = Reduce( '%p%', list(...) )
display_prod( prod ) }
display_prod( prod ) }
</syntaxhighlight>
</lang>


Simple tests:
Simple tests:


<syntaxhighlight lang=R>
<lang R>
> display_prod( c(1, 2) %p% c(3, 4) )
> display_prod( c(1, 2) %p% c(3, 4) )
1, 3
1, 3
Line 3,665: Line 3,665:
> display_prod( c(3, 4) %p% c() )
> display_prod( c(3, 4) %p% c() )
>
>
</syntaxhighlight>
</lang>


Tougher tests:
Tougher tests:


<syntaxhighlight lang=R>
<lang R>
go( c(1776, 1789), c(7, 12), c(4, 14, 23), c(0, 1) )
go( c(1776, 1789), c(7, 12), c(4, 14, 23), c(0, 1) )
go( c(1, 2, 3), c(30), c(500, 100) )
go( c(1, 2, 3), c(30), c(500, 100) )
go( c(1, 2, 3), c(), c(500, 100) )
go( c(1, 2, 3), c(), c(500, 100) )
</syntaxhighlight>
</lang>


{{out}}
{{out}}
Line 3,718: Line 3,718:
Racket has a built-in "cartesian-product" function:
Racket has a built-in "cartesian-product" function:


<lang>#lang racket/base
<syntaxhighlight lang=text>#lang racket/base
(require rackunit
(require rackunit
;; usually, included in "racket", but we're using racket/base so we
;; usually, included in "racket", but we're using racket/base so we
Line 3,734: Line 3,734:
(cartesian-product '(1776 1789) '(7 12) '(4 14 23) '(0 1))
(cartesian-product '(1776 1789) '(7 12) '(4 14 23) '(0 1))
(cartesian-product '(1 2 3) '(30) '(500 100))
(cartesian-product '(1 2 3) '(30) '(500 100))
(cartesian-product '(1 2 3) '() '(500 100))</lang>
(cartesian-product '(1 2 3) '() '(500 100))</syntaxhighlight>


{{out}}
{{out}}
Line 3,770: Line 3,770:
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 reduce cross meta operator [X].
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 reduce cross meta operator [X].


<lang perl6># cartesian product of two lists using the X cross meta-operator
<syntaxhighlight lang=raku line># cartesian product of two lists using the X cross meta-operator
say (1, 2) X (3, 4);
say (1, 2) X (3, 4);
say (3, 4) X (1, 2);
say (3, 4) X (1, 2);
Line 3,780: Line 3,780:
say [X] (1776, 1789), (7, 12), (4, 14, 23), (0, 1);
say [X] (1776, 1789), (7, 12), (4, 14, 23), (0, 1);
say [X] (1, 2, 3), (30), (500, 100);
say [X] (1, 2, 3), (30), (500, 100);
say [X] (1, 2, 3), (), (500, 100);</lang>
say [X] (1, 2, 3), (), (500, 100);</syntaxhighlight>
{{out}}
{{out}}
<pre>((1 3) (1 4) (2 3) (2 4))
<pre>((1 3) (1 4) (2 3) (2 4))
Line 3,793: Line 3,793:
===version 1===
===version 1===
This REXX version isn't limited by the number of lists or the number of sets within a list.
This REXX version isn't limited by the number of lists or the number of sets within a list.
<lang rexx>/*REXX program calculates the Cartesian product of two arbitrary-sized lists. */
<syntaxhighlight lang=rexx>/*REXX program calculates the Cartesian product of two arbitrary-sized lists. */
@.= /*assign the default value to @. array*/
@.= /*assign the default value to @. array*/
parse arg @.1 /*obtain the optional value of @.1 */
parse arg @.1 /*obtain the optional value of @.1 */
Line 3,819: Line 3,819:
end /*i*/
end /*i*/
say 'Cartesian product of ' space(@.n) " is ───► {"substr($, 2)'}'
say 'Cartesian product of ' space(@.n) " is ───► {"substr($, 2)'}'
end /*n*/ /*stick a fork in it, we're all done. */</lang>
end /*n*/ /*stick a fork in it, we're all done. */</syntaxhighlight>
{{out|output|text=&nbsp; when using the default lists:}}
{{out|output|text=&nbsp; when using the default lists:}}
<pre>
<pre>
Line 3,830: Line 3,830:


===version 2===
===version 2===
<lang rexx>/* REXX computes the Cartesian Product of up to 4 sets */
<syntaxhighlight lang=rexx>/* REXX computes the Cartesian Product of up to 4 sets */
Call cart '{1, 2} x {3, 4}'
Call cart '{1, 2} x {3, 4}'
Call cart '{3, 4} x {1, 2}'
Call cart '{3, 4} x {1, 2}'
Line 3,893: Line 3,893:
End
End
Say ' '
Say ' '
Return 0</lang>
Return 0</syntaxhighlight>
{{out}}
{{out}}
<pre>{1, 2} x {3, 4}
<pre>{1, 2} x {3, 4}
Line 3,951: Line 3,951:


=={{header|Ring}}==
=={{header|Ring}}==
<lang ring>
<syntaxhighlight lang=ring>
# Project : Cartesian product of two or more lists
# Project : Cartesian product of two or more lists


Line 3,966: Line 3,966:
next
next
see nl
see nl
</syntaxhighlight>
</lang>
Output:
Output:
<pre>
<pre>
Line 3,982: Line 3,982:
=={{header|Ruby}}==
=={{header|Ruby}}==
"product" is a method of arrays. It takes one or more arrays as argument and results in the Cartesian product:
"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])
<syntaxhighlight lang=ruby>p [1, 2].product([3, 4])
p [3, 4].product([1, 2])
p [3, 4].product([1, 2])
p [1, 2].product([])
p [1, 2].product([])
Line 3,989: Line 3,989:
p [1, 2, 3].product([30], [500, 100])
p [1, 2, 3].product([30], [500, 100])
p [1, 2, 3].product([], [500, 100])
p [1, 2, 3].product([], [500, 100])
</syntaxhighlight>
</lang>
{{out}}<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
{{out}}<pre>[[1, 3], [1, 4], [2, 3], [2, 4]]
[[3, 1], [3, 2], [4, 1], [4, 2]]
[[3, 1], [3, 2], [4, 1], [4, 2]]
Line 4,000: Line 4,000:


=={{header|Rust}}==
=={{header|Rust}}==
<lang rust>fn cartesian_product(lists: &Vec<Vec<u32>>) -> Vec<Vec<u32>> {
<syntaxhighlight lang=rust>fn cartesian_product(lists: &Vec<Vec<u32>>) -> Vec<Vec<u32>> {
let mut res = vec![];
let mut res = vec![];


Line 4,041: Line 4,041:
}
}
}
}
</syntaxhighlight>
</lang>
{{out}}<pre>[1, 2] × [3, 4]
{{out}}<pre>[1, 2] × [3, 4]
[[1, 3], [1, 4], [2, 3], [2, 4]]
[[1, 3], [1, 4], [2, 3], [2, 4]]
Line 4,067: Line 4,067:
Function returning the n-ary product of an arbitrary number of lists, each of arbitrary length:
Function returning the n-ary product of an arbitrary number of lists, each of arbitrary length:


<lang scala>def cartesianProduct[T](lst: List[T]*): List[List[T]] = {
<syntaxhighlight lang=scala>def cartesianProduct[T](lst: List[T]*): List[List[T]] = {


/**
/**
Line 4,096: Line 4,096:
}
}
}
}
}</lang>
}</syntaxhighlight>
and usage:
and usage:
<lang scala>cartesianProduct(List(1, 2), List(3, 4))
<syntaxhighlight lang=scala>cartesianProduct(List(1, 2), List(3, 4))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}</pre>
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}</pre>


<lang scala>cartesianProduct(List(3, 4), List(1, 2))
<syntaxhighlight lang=scala>cartesianProduct(List(3, 4), List(1, 2))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{(3, 1), (3, 2), (4, 1), (4, 2)}</pre>
<pre>{(3, 1), (3, 2), (4, 1), (4, 2)}</pre>


<lang scala>cartesianProduct(List(1, 2), List.empty)
<syntaxhighlight lang=scala>cartesianProduct(List(1, 2), List.empty)
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{}</pre>
<pre>{}</pre>


<lang scala>cartesianProduct(List.empty, List(1, 2))
<syntaxhighlight lang=scala>cartesianProduct(List.empty, List(1, 2))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{}</pre>
<pre>{}</pre>


<lang scala>cartesianProduct(List(1776, 1789), List(7, 12), List(4, 14, 23), List(0, 1))
<syntaxhighlight lang=scala>cartesianProduct(List(1776, 1789), List(7, 12), List(4, 14, 23), List(0, 1))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{(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)}</pre>
<pre>{(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)}</pre>


<lang scala>cartesianProduct(List(1, 2, 3), List(30), List(500, 100))
<syntaxhighlight lang=scala>cartesianProduct(List(1, 2, 3), List(30), List(500, 100))
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</lang>
.map(_.mkString("(", ", ", ")")).mkString("{",", ","}")</syntaxhighlight>
{{out}}
{{out}}
<pre>{(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)}</pre>
<pre>{(1, 30, 500), (1, 30, 100), (2, 30, 500), (2, 30, 100), (3, 30, 500), (3, 30, 100)}</pre>


<lang scala>cartesianProduct(List(1, 2, 3), List.empty, List(500, 100))
<syntaxhighlight lang=scala>cartesianProduct(List(1, 2, 3), List.empty, List(500, 100))
.map(_.mkString("[", ", ", "]")).mkString("\n")</lang>
.map(_.mkString("[", ", ", "]")).mkString("\n")</syntaxhighlight>
{{out}}
{{out}}
<pre>{}</pre>
<pre>{}</pre>


=={{header|Scheme}}==
=={{header|Scheme}}==
<lang scheme>
<syntaxhighlight lang=scheme>
(define cartesian-product (lambda (xs ys)
(define cartesian-product (lambda (xs ys)
(if (or (zero? (length xs)) (zero? (length ys)))
(if (or (zero? (length xs)) (zero? (length ys)))
Line 4,155: Line 4,155:
> (nary-cartesian-product '((1 2)(a b)(x y)))
> (nary-cartesian-product '((1 2)(a b)(x y)))
((1 a x) (1 a y) (1 b x) (1 b y) (2 a x) (2 a y) (2 b x) (2 b y))
((1 a x) (1 a y) (1 b x) (1 b y) (2 a x) (2 a y) (2 b x) (2 b y))
</syntaxhighlight>
</lang>


=={{header|Sidef}}==
=={{header|Sidef}}==
In Sidef, the Cartesian product of an arbitrary number of arrays is built-in as ''Array.cartesian()'':
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
<syntaxhighlight lang=ruby>cartesian([[1,2], [3,4], [5,6]]).say
cartesian([[1,2], [3,4], [5,6]], {|*arr| say arr })</lang>
cartesian([[1,2], [3,4], [5,6]], {|*arr| say arr })</syntaxhighlight>


Alternatively, a simple recursive implementation:
Alternatively, a simple recursive implementation:
<lang ruby>func cartesian_product(*arr) {
<syntaxhighlight lang=ruby>func cartesian_product(*arr) {


var c = []
var c = []
Line 4,182: Line 4,182:


return r
return r
}</lang>
}</syntaxhighlight>


Completing the task:
Completing the task:
<lang ruby>say cartesian_product([1,2], [3,4])
<syntaxhighlight lang=ruby>say cartesian_product([1,2], [3,4])
say cartesian_product([3,4], [1,2])</lang>
say cartesian_product([3,4], [1,2])</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,193: Line 4,193:
</pre>
</pre>
The product of an empty list with any other list is empty:
The product of an empty list with any other list is empty:
<lang ruby>say cartesian_product([1,2], [])
<syntaxhighlight lang=ruby>say cartesian_product([1,2], [])
say cartesian_product([], [1,2])</lang>
say cartesian_product([], [1,2])</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,201: Line 4,201:
</pre>
</pre>
Extra credit:
Extra credit:
<lang ruby>cartesian_product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]).each{ .say }</lang>
<syntaxhighlight lang=ruby>cartesian_product([1776, 1789], [7, 12], [4, 14, 23], [0, 1]).each{ .say }</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,230: Line 4,230:
</pre>
</pre>


<lang ruby>say cartesian_product([1, 2, 3], [30], [500, 100])
<syntaxhighlight lang=ruby>say cartesian_product([1, 2, 3], [30], [500, 100])
say cartesian_product([1, 2, 3], [], [500, 100])</lang>
say cartesian_product([1, 2, 3], [], [500, 100])</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,240: Line 4,240:
=={{header|SQL}}==
=={{header|SQL}}==
If we create lists as tables with one column, cartesian product is easy.
If we create lists as tables with one column, cartesian product is easy.
<lang sql>-- set up list 1
<syntaxhighlight lang=sql>-- set up list 1
create table L1 (value integer);
create table L1 (value integer);
insert into L1 values (1);
insert into L1 values (1);
Line 4,249: Line 4,249:
insert into L2 values (4);
insert into L2 values (4);
-- get the product
-- get the product
select * from L1, L2;</lang>
select * from L1, L2;</syntaxhighlight>
{{out}}
{{out}}
<pre> VALUE VALUE
<pre> VALUE VALUE
Line 4,256: Line 4,256:
1 4
1 4
2 3
2 3
2 4</pre>You should be able to be more explicit should get the same result:<lang sql>select * from L1 cross join L2;</lang>
2 4</pre>You should be able to be more explicit should get the same result:<syntaxhighlight lang=sql>select * from L1 cross join L2;</syntaxhighlight>
Product with an empty list works as expected (using the tables created above):
Product with an empty list works as expected (using the tables created above):
<lang sql>delete from L2;
<syntaxhighlight lang=sql>delete from L2;
select * from L1, L2;</lang>
select * from L1, L2;</syntaxhighlight>
{{out}}
{{out}}
<pre>no rows selected</pre>
<pre>no rows selected</pre>
I don't think "extra credit" is meaningful here because cartesian product is so hard-baked into SQL, so here's just one of the extra credit examples (again using the tables created above):<lang sql>insert into L1 values (3);
I don't think "extra credit" is meaningful here because cartesian product is so hard-baked into SQL, so here's just one of the extra credit examples (again using the tables created above):<syntaxhighlight lang=sql>insert into L1 values (3);
insert into L2 values (30);
insert into L2 values (30);
create table L3 (value integer);
create table L3 (value integer);
Line 4,268: Line 4,268:
insert into L3 values (100);
insert into L3 values (100);
-- product works the same for as many "lists" as you'd like
-- product works the same for as many "lists" as you'd like
select * from L1, L2, L3;</lang>
select * from L1, L2, L3;</syntaxhighlight>
{{out}}
{{out}}
<pre> VALUE VALUE VALUE
<pre> VALUE VALUE VALUE
Line 4,280: Line 4,280:


=={{header|Standard ML}}==
=={{header|Standard ML}}==
<lang sml>fun prodList (nil, _) = nil
<syntaxhighlight lang=sml>fun prodList (nil, _) = nil
| prodList ((x::xs), ys) = map (fn y => (x,y)) ys @ prodList (xs, ys)
| 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)</lang>
fun naryProdList zs = foldl (fn (xs, ys) => map op:: (prodList (xs, ys))) [[]] (rev zs)</syntaxhighlight>


{{out}}
{{out}}
Line 4,312: Line 4,312:
In Stata, the command '''[https://www.stata.com/help.cgi?fillin 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.
In Stata, the command '''[https://www.stata.com/help.cgi?fillin 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.


<lang stata>. list
<syntaxhighlight lang=stata>. list


+-------+
+-------+
Line 4,331: Line 4,331:
3. | 2 3 1 |
3. | 2 3 1 |
4. | 2 4 0 |
4. | 2 4 0 |
+-----------------+</lang>
+-----------------+</syntaxhighlight>


The other way around:
The other way around:


<lang stata>. list
<syntaxhighlight lang=stata>. list


+-------+
+-------+
Line 4,354: Line 4,354:
3. | 4 1 1 |
3. | 4 1 1 |
4. | 4 2 0 |
4. | 4 2 0 |
+-----------------+</lang>
+-----------------+</syntaxhighlight>


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


<lang stata>. list
<syntaxhighlight lang=stata>. list


+-------+
+-------+
Line 4,375: Line 4,375:
1. | 1 . 0 |
1. | 1 . 0 |
2. | 2 . 0 |
2. | 2 . 0 |
+-----------------+</lang>
+-----------------+</syntaxhighlight>


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


<lang stata>. list
<syntaxhighlight lang=stata>. list


+-----------+
+-----------+
Line 4,434: Line 4,434:
|---------------------|
|---------------------|
6. | 3 5 6 1 |
6. | 3 5 6 1 |
+---------------------+</lang>
+---------------------+</syntaxhighlight>


=={{header|Swift}}==
=={{header|Swift}}==
Line 4,440: Line 4,440:
{{trans|Scala}}
{{trans|Scala}}


<lang swift>func + <T>(el: T, arr: [T]) -> [T] {
<syntaxhighlight lang=swift>func + <T>(el: T, arr: [T]) -> [T] {
var ret = arr
var ret = arr


Line 4,482: Line 4,482:
print(cartesianProduct([1776, 1789], [7, 12], [4, 14, 23], [0, 1]))
print(cartesianProduct([1776, 1789], [7, 12], [4, 14, 23], [0, 1]))
print(cartesianProduct([1, 2, 3], [30], [500, 100]))
print(cartesianProduct([1, 2, 3], [30], [500, 100]))
print(cartesianProduct([1, 2, 3], [], [500, 100])</lang>
print(cartesianProduct([1, 2, 3], [], [500, 100])</syntaxhighlight>


{{out}}
{{out}}
Line 4,494: Line 4,494:


=={{header|Tailspin}}==
=={{header|Tailspin}}==
<lang tailspin>
<syntaxhighlight lang=tailspin>
'{1,2}x{3,4} = $:[by [1,2]..., by [3,4]...];
'{1,2}x{3,4} = $:[by [1,2]..., by [3,4]...];
' -> !OUT::write
' -> !OUT::write
Line 4,519: Line 4,519:
'year {1776, 1789} × month {7, 12} × day {4, 14, 23} = $:{by [1776, 1789]... -> (year:$), by [7, 12]... -> (month:$), by [4, 14, 23]... -> (day:$)};
'year {1776, 1789} × month {7, 12} × day {4, 14, 23} = $:{by [1776, 1789]... -> (year:$), by [7, 12]... -> (month:$), by [4, 14, 23]... -> (day:$)};
' -> !OUT::write
' -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 4,533: Line 4,533:


=={{header|Tcl}}==
=={{header|Tcl}}==
<lang tcl>
<syntaxhighlight lang=tcl>
proc cartesianProduct {l1 l2} {
proc cartesianProduct {l1 l2} {
set result {}
set result {}
Line 4,569: Line 4,569:
puts "result: [cartesianNaryProduct {{1 2 3} {} {500 100}}]"
puts "result: [cartesianNaryProduct {{1 2 3} {} {500 100}}]"


</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 4,628: Line 4,628:
=={{header|Visual Basic .NET}}==
=={{header|Visual Basic .NET}}==
{{trans|C#}}
{{trans|C#}}
<lang vbnet>Imports System.Runtime.CompilerServices
<syntaxhighlight lang=vbnet>Imports System.Runtime.CompilerServices


Module Module1
Module Module1
Line 4,664: Line 4,664:
End Sub
End Sub


End Module</lang>
End Module</syntaxhighlight>
{{out}}
{{out}}
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}
<pre>{(1, 3), (1, 4), (2, 3), (2, 4)}
Line 4,677: Line 4,677:
{{trans|Kotlin}}
{{trans|Kotlin}}
{{libheader|Wren-seq}}
{{libheader|Wren-seq}}
<lang ecmascript>import "/seq" for Lst
<syntaxhighlight lang=ecmascript>import "/seq" for Lst


var prod2 = Fn.new { |l1, l2|
var prod2 = Fn.new { |l1, l2|
Line 4,709: Line 4,709:
printProdN.call([ [1, 2, 3], [30], [500, 100] ])
printProdN.call([ [1, 2, 3], [30], [500, 100] ])
printProdN.call([ [1, 2, 3], [], [500, 100] ])
printProdN.call([ [1, 2, 3], [], [500, 100] ])
printProdN.call([ [1, 2, 3], [30], ["a", "b"] ])</lang>
printProdN.call([ [1, 2, 3], [30], ["a", "b"] ])</syntaxhighlight>


{{out}}
{{out}}
Line 4,776: Line 4,776:
Cartesian product is build into iterators or can be done with nested
Cartesian product is build into iterators or can be done with nested
loops.
loops.
<lang zkl>zkl: Walker.cproduct(List(1,2),List(3,4)).walk().println();
<syntaxhighlight 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))
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)) }
zkl: foreach a,b in (List(1,2),List(3,4)){ print("(%d,%d) ".fmt(a,b)) }
Line 4,782: Line 4,782:


zkl: Walker.cproduct(List(3,4),List(1,2)).walk().println();
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>
L(L(3,1),L(3,2),L(4,1),L(4,2))</syntaxhighlight>


The walk method will throw an error if used on an empty iterator but the pump
The walk method will throw an error if used on an empty iterator but the pump
method doesn't.
method doesn't.
<lang zkl>zkl: Walker.cproduct(List(3,4),List).walk().println();
<syntaxhighlight lang=zkl>zkl: Walker.cproduct(List(3,4),List).walk().println();
Exception thrown: TheEnd(Ain't no more)
Exception thrown: TheEnd(Ain't no more)


Line 4,792: Line 4,792:
L()
L()
zkl: Walker.cproduct(List,List(3,4)).pump(List).println();
zkl: Walker.cproduct(List,List(3,4)).pump(List).println();
L()</lang>
L()</syntaxhighlight>
<lang zkl>zkl: Walker.cproduct(L(1776,1789),L(7,12),L(4,14,23),L(0,1)).walk().println();
<syntaxhighlight 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),...)
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),...)


Line 4,800: Line 4,800:


zkl: Walker.cproduct(L(1,2,3),List,L(500,100)).pump(List).println();
zkl: Walker.cproduct(L(1,2,3),List,L(500,100)).pump(List).println();
L()</lang>
L()</syntaxhighlight>