I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Cartesian product of two or more lists

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.

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}

## 11l

Translation of: Go
`F cart_prod(a, b)   V p = [(0, 0)] * (a.len * b.len)   V i = 0   L(aa) a      L(bb) b         p[i++] = (aa, bb)   R p print(cart_prod([1, 2], [3, 4]))print(cart_prod([3, 4], [1, 2]))[Int] empty_arrayprint(cart_prod([1, 2], empty_array))print(cart_prod(empty_array, [1, 2]))`

#### Alternative version

`F cart_prod(a, b)   R multiloop(a, b, (aa, bb) -> (aa, bb))`
Output:
```[(1, 3), (1, 4), (2, 3), (2, 4)]
[(3, 1), (3, 2), (4, 1), (4, 2)]
[]
[]
```

## Action!

`DEFINE MAX_COUNT="10"DEFINE MAX_RESULT="100" DEFINE PTR="CARD" PROC PrintInput(PTR ARRAY a INT count)  INT i,j,n  INT ARRAY tmp   FOR i=0 TO count-1  DO    tmp=a(i) n=tmp(0)    Put('[)    FOR j=1 TO n    DO      PrintI(tmp(j))      IF j<n THEN Put(',) FI    OD    Put('])    IF i<count-1 THEN Put('x) FI  ODRETURN PROC PrintOutput(INT ARRAY a INT groups,count)  INT i,j,k   Put('[)  k=0  FOR i=0 TO groups-1  DO    Put('()    FOR j=0 TO count-1    DO      PrintI(a(k)) k==+1      IF j<count-1 THEN Put(',) FI    OD    Put('))    IF i<groups-1 THEN Put(',) FI  OD  Put('])RETURN PROC Product(PTR ARRAY a INT count  INT ARRAY r INT POINTER groups)  INT ARRAY ind(MAX_COUNT),tmp  INT i,j,k   IF count>MAX_COUNT THEN Break() FI  groups^=1  FOR i=0 TO count-1  DO    ind(i)=1 tmp=a(i)    groups^==*tmp(0)  OD  IF groups^=0 THEN RETURN FI   j=count-1 k=0  DO    FOR i=0 TO count-1    DO      tmp=a(i)      r(k)=tmp(ind(i)) k==+1    OD     DO      tmp=a(j)      IF ind(j)<tmp(0) THEN        ind(j)==+1        FOR i=j+1 TO count-1        DO          ind(i)=1        OD        j=count-1        EXIT      ELSE        IF j=0 THEN RETURN FI        j==-1      FI    OD  ODRETURN PROC Test(PTR ARRAY a INT count)  INT ARRAY r(MAX_RESULT)  INT groups   IF count<2 THEN Break() FI  Product(a,count,r,@groups)  PrintInput(a,count)  Put('=)  PrintOutput(r,groups,count)  PutE()RETURN PROC Main()  INT ARRAY    a1=[2 1 2],a2=[2 3 4],a3=[0],    a4=[2 1776 1789],a5=[2 7 12],    a6=[3 4 14 23],a7=[2 0 1],    a8=[3 1 2 3],a9=[1 30],a10=[2 500 100]  PTR ARRAY a(4)   a(0)=a1 a(1)=a2 Test(a,2)  a(0)=a2 a(1)=a1 Test(a,2)  a(0)=a1 a(1)=a3 Test(a,2)  a(0)=a3 a(1)=a1 Test(a,2) PutE()  a(0)=a4 a(1)=a5 a(2)=a6 a(3)=a7 Test(a,4) 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)RETURN`
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]=[]
[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]=[]
```

`with Ada.Text_IO;  use Ada.Text_Io;with Ada.Containers.Doubly_Linked_Lists;with Ada.Strings.Fixed; procedure Cartesian is    type Element_Type is new Long_Integer;    package Lists is      new Ada.Containers.Doubly_Linked_Lists (Element_Type);   package List_Lists is      new Ada.Containers.Doubly_Linked_Lists (Lists.List, Lists."=");    subtype List      is Lists.List;   subtype List_List is List_Lists.List;    function "*" (Left, Right : List) return List_List is      Result : List_List;      Sub    : List;   begin      for Outer of Left loop         for Inner of Right loop            Sub.Clear;            Sub.Append (Outer);            Sub.Append (Inner);            Result.Append (Sub);         end loop;      end loop;      return Result;   end "*";    function "*" (Left  : List_List;                 Right : List) return List_List   is      Result : List_List;      Sub    : List;   begin      for Outer of Left loop         for Inner of Right loop            Sub := Outer;            Sub.Append (Inner);            Result.Append (Sub);         end loop;      end loop;      return Result;   end "*";    procedure Put (L : List) is      use Ada.Strings;      First : Boolean := True;   begin      Put ("(");      for E of L loop         if not First then            Put (",");         end if;         Put (Fixed.Trim (E'Image, Left));         First := False;      end loop;      Put (")");   end Put;    procedure Put (LL : List_List) is      First : Boolean := True;   begin      Put ("{");      for E of LL loop         if not First then            Put (",");         end if;         Put (E);         First := False;      end loop;      Put ("}");   end Put;    function "&" (Left : List; Right : Element_Type) return List is      Result : List := Left;   begin      Result.Append (Right);      return Result;   end "&";    Nil        : List renames Lists.Empty_List;   List_1_2   : constant List := Nil & 1 & 2;   List_3_4   : constant List := Nil & 3 & 4;   List_Empty : constant List := Nil;   List_1_2_3 : constant List := Nil & 1 & 2 & 3;begin   Put (List_1_2 * List_3_4); New_Line;    Put (List_3_4 * List_1_2); New_Line;    Put (List_Empty * List_1_2); New_Line;    Put (List_1_2 * List_Empty); New_Line;    Put (List'(Nil & 1776 & 1789) * List'(Nil & 7 & 12) *          List'(Nil & 4 & 14 & 23) * List'(Nil & 0 & 1)); New_Line;    Put (List_1_2_3 * List'(Nil & 30) * List'(Nil & 500 & 100)); New_Line;    Put (List_1_2_3 * List_Empty * List'(Nil & 500 & 100)); New_Line;end Cartesian;`
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)}
{}```

## APL

APL has a built-in outer product operator: `X ∘.F Y` will get you an ⍴X-by-⍴Y matrix containing every corresponding value of `x F y` for all x∊X, y∊Y.

The Cartesian product can therefore be expressed as `∘.,`, but as that would return a matrix, and the task is asking for a list, you also need to ravel the result.

`cart ← ,∘.,`
Output:
```      1 2 cart 3 4
1 3  1 4  2 3  2 4
3 4 cart 1 2
3 1  3 2  4 1  4 2
1 2 cart ⍬   ⍝ empty output

⍬ cart 1 2   ⍝ empty output again

```

This can be reduced over a list of lists to generate the Cartesian product of an arbitrary list of lists.

`nary_cart ← ⊃(,∘.,)/`
Output:

The items are listed on separate lines (using ↑) for clarity.

```      ↑nary_cart (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
↑nary_cart(1 2 3)(,30)(50 100)
1 30  50
1 30 100
2 30  50
2 30 100
3 30  50
3 30 100
↑nary_cart(1 2 3)(⍬)(50 100)  ⍝ empty output
```

## AppleScript

`-- CARTESIAN PRODUCTS --------------------------------------------------------- -- Two lists: -- cartProd :: [a] -> [b] -> [(a, b)]on cartProd(xs, ys)    script        on |λ|(x)            script                on |λ|(y)                    [[x, y]]                end |λ|            end script            concatMap(result, ys)        end |λ|    end script    concatMap(result, xs)end cartProd -- N-ary – a function over a list of lists: -- cartProdNary :: [[a]] -> [[a]]on cartProdNary(xss)    script        on |λ|(accs, xs)            script                on |λ|(x)                    script                        on |λ|(a)                            {x & a}                        end |λ|                    end script                    concatMap(result, accs)                end |λ|            end script            concatMap(result, xs)        end |λ|    end script    foldr(result, {{}}, xss)end cartProdNary -- TESTS ----------------------------------------------------------------------on run    set baseExamples to unlines(map(show, ¬        [cartProd({1, 2}, {3, 4}), ¬            cartProd({3, 4}, {1, 2}), ¬            cartProd({1, 2}, {}), ¬            cartProd({}, {1, 2})]))     set naryA to unlines(map(show, ¬        cartProdNary([{1776, 1789}, {7, 12}, {4, 14, 23}, {0, 1}])))     set naryB to show(cartProdNary([{1, 2, 3}, {30}, {500, 100}]))     set naryC to show(cartProdNary([{1, 2, 3}, {}, {500, 100}]))     intercalate(linefeed & linefeed, {baseExamples, naryA, naryB, naryC})end run  -- GENERIC FUNCTIONS ---------------------------------------------------------- -- concatMap :: (a -> [b]) -> [a] -> [b]on concatMap(f, xs)    set lst to {}    set lng to length of xs    tell mReturn(f)        repeat with i from 1 to lng            set lst to (lst & |λ|(item i of xs, i, xs))        end repeat    end tell    return lstend concatMap -- foldr :: (a -> b -> a) -> a -> [b] -> aon 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 tellend foldr -- intercalate :: Text -> [Text] -> Texton 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 strJoinedend 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 tellend map -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Scripton mReturn(f)    if class of f is script then        f    else        script            property |λ| : f        end script    end ifend mReturn -- show :: a -> Stringon 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 ifend show -- unlines :: [String] -> Stringon 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]]

[]```

## Arturo

Translation of: Ruby
`loop [    [[1 2][3 4]]     [[3 4][1 2]]    [[1 2][]]    [[][1 2]]     [[1776 1789][7 12][4 14 23][0 1]]    [[1 2 3][30][500 100]]     [[1 2 3][][500 100]] ] 'lst [    print as.code product.cartesian lst]`
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]]
[]```

## Bracmat

`( ( mul  =   R a b A B    .   :?R      & !arg:(.?A) (.?B)      & (   !A          :   ?              ( %@?a              &   !B                :   ?                    ( (%@?b|(.?b))                    & !R (.!a !b):?R                    & ~                    )                    ?              )              ?        | (.!R)        )  )& ( cartprod  =   a    .   !arg:%?a %?arg&mul\$(!a cartprod\$!arg)      | !arg  )&   out  \$ ( cartprod    \$ ( (.1776 1789)        (.7 12)        (.4 14 23)        (.0 1)      )    )& out\$(cartprod\$((.1 2 3) (.30) (.500 100)))& out\$(cartprod\$((.1 2 3) (.) (.500 100))))`
```.   (.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

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.

` #include<string.h>#include<stdlib.h>#include<stdio.h> void cartesianProduct(int** sets, int* setLengths, int* currentSet, int numSets, int times){	int i,j; 	if(times==numSets){		printf("(");		for(i=0;i<times;i++){			printf("%d,",currentSet[i]);		}		printf("\b),");	}	else{		for(j=0;j<setLengths[times];j++){			currentSet[times] = sets[times][j];			cartesianProduct(sets,setLengths,currentSet,numSets,times+1);		}	}} void printSets(int** sets, int* setLengths, int numSets){	int i,j; 	printf("\nNumber of sets : %d",numSets); 	for(i=0;i<numSets+1;i++){		printf("\nSet %d : ",i+1);		for(j=0;j<setLengths[i];j++){			printf(" %d ",sets[i][j]);		}	}} void processInputString(char* str){	int **sets, *currentSet, *setLengths, setLength, numSets = 0, i,j,k,l,start,counter=0;	char *token,*holder,*holderToken; 	for(i=0;str[i]!=00;i++)		if(str[i]=='x')			numSets++; 	if(numSets==0){			printf("\n%s",str);			return;	} 	currentSet = (int*)calloc(sizeof(int),numSets + 1); 	setLengths = (int*)calloc(sizeof(int),numSets + 1); 	sets = (int**)malloc((numSets + 1)*sizeof(int*)); 	token = strtok(str,"x"); 	while(token!=NULL){		holder = (char*)malloc(strlen(token)*sizeof(char)); 		j = 0; 		for(i=0;token[i]!=00;i++){			if(token[i]>='0' && token[i]<='9')				holder[j++] = token[i];			else if(token[i]==',')				holder[j++] = ' ';		}		holder[j] = 00; 		setLength = 0; 		for(i=0;holder[i]!=00;i++)			if(holder[i]==' ')				setLength++; 		if(setLength==0 && strlen(holder)==0){			printf("\n{}");			return;		} 		setLengths[counter] = setLength+1; 		sets[counter] = (int*)malloc((1+setLength)*sizeof(int)); 		k = 0; 		start = 0; 		for(l=0;holder[l]!=00;l++){			if(holder[l+1]==' '||holder[l+1]==00){				holderToken = (char*)malloc((l+1-start)*sizeof(char));				strncpy(holderToken,holder + start,l+1-start);				sets[counter][k++] = atoi(holderToken);				start = l+2;			}		} 		counter++;		token = strtok(NULL,"x");	} 	printf("\n{");	cartesianProduct(sets,setLengths,currentSet,numSets + 1,0);	printf("\b}"); } int main(int argC,char* argV[]){	if(argC!=2)		printf("Usage : %s <Set product expression enclosed in double quotes>",argV[0]);	else		processInputString(argV[1]); 	return 0;} `

Invocation and output :

```C:\My Projects\threeJS>cartesianProduct.exe "{1,2} x {3,4}"

{(1,3),(1,4),(2,3),(2,4)}
C:\My Projects\threeJS>cartesianProduct.exe "{3,4} x {1,2}"

{(3,1),(3,2),(4,1),(4,2)}
C:\My Projects\threeJS>cartesianProduct.exe "{1,2} x {}"

{}
C:\My Projects\threeJS>cartesianProduct.exe "{} x {1,2}"

{}
C:\My Projects\threeJS>cartesianProduct.exe "{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,9,12,14,1),(1789,12,23,0),(1789,12,23,1)}
C:\My Projects\threeJS>cartesianProduct.exe "{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)}
C:\My Projects\threeJS>cartesianProduct.exe "{1, 2, 3} x {} x {500, 100}"

{}
```

## C#

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

## C++

` #include <iostream>#include <vector>#include <algorithm> void print(const std::vector<std::vector<int>>& v) {  std::cout << "{ ";  for (const auto& p : v) {    std::cout << "(";    for (const auto& e : p) {      std::cout << e << " ";    }    std::cout << ") ";  }  std::cout << "}" << std::endl;} auto product(const std::vector<std::vector<int>>& lists) {  std::vector<std::vector<int>> result;  if (std::find_if(std::begin(lists), std::end(lists),     [](auto e) -> bool { return e.size() == 0; }) != std::end(lists)) {    return result;  }  for (auto& e : lists[0]) {    result.push_back({ e });  }  for (size_t i = 1; i < lists.size(); ++i) {    std::vector<std::vector<int>> temp;    for (auto& e : result) {      for (auto f : lists[i]) {        auto e_tmp = e;        e_tmp.push_back(f);        temp.push_back(e_tmp);      }    }    result = temp;  }  return result;} int main() {  std::vector<std::vector<int>> prods[] = {    { { 1, 2 }, { 3, 4 } },    { { 3, 4 }, { 1, 2} },    { { 1, 2 }, { } },    { { }, { 1, 2 } },    { { 1776, 1789 }, { 7, 12 }, { 4, 14, 23 }, { 0, 1 } },    { { 1, 2, 3 }, { 30 }, { 500, 100 } },    { { 1, 2, 3 }, { }, { 500, 100 } }  };  for (const auto& p : prods) {    print(product(p));  }  std::cin.ignore();  std::cin.get();  return 0;}`
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) }
{ }```

## Clojure

`  (ns clojure.examples.product	(:gen-class)	(:require [clojure.pprint :as pp])) (defn cart [colls]  "Compute the cartesian product of list of lists"  (if (empty? colls)    '(())    (for [more (cart (rest colls))          x (first colls)]      (cons x more)))) `

Output

` (doseq [lst [   [[1,2],[3,4]],                 [[3,4],[1,2]], [[], [1, 2]],                 [[1, 2], []],                [[1776, 1789],  [7, 12], [4, 14, 23], [0, 1]],                [[1, 2, 3], [30,], [500, 100]],                [[1, 2, 3], [], [500, 100]]            ]        ]    (println lst "=>")    (pp/pprint (cart lst))) `
```[[1 2] [3 4]] =>
((1 3) (2 3) (1 4) (2 4))
[[3 4] [1 2]] =>
((3 1) (4 1) (3 2) (4 2))
[[] [1 2]] =>
()
[[1 2] []] =>
()
[[1776 1789] [7 12] [4 14 23] [0 1]] =>
((1776 7 4 0)
(1789 7 4 0)
(1776 12 4 0)
(1789 12 4 0)
(1776 7 14 0)
(1789 7 14 0)
(1776 12 14 0)
(1789 12 14 0)
(1776 7 23 0)
(1789 7 23 0)
(1776 12 23 0)
(1789 12 23 0)
(1776 7 4 1)
(1789 7 4 1)
(1776 12 4 1)
(1789 12 4 1)
(1776 7 14 1)
(1789 7 14 1)
(1776 12 14 1)
(1789 12 14 1)
(1776 7 23 1)
(1789 7 23 1)
(1776 12 23 1)
(1789 12 23 1))
[[1 2 3] [30] [500 100]] =>
((1 30 500) (2 30 500) (3 30 500) (1 30 100) (2 30 100) (3 30 100))
[[1 2 3] [] [500 100]] =>
()
```

## Common Lisp

`(defun cartesian-product (s1 s2)  "Compute the cartesian product of two sets represented as lists"  (loop for x in s1	nconc (loop for y in s2 collect (list x y)))) `

Output

` CL-USER> (cartesian-product '(1 2) '(3 4))((1 3) (1 4) (2 3) (2 4))CL-USER> (cartesian-product '(3 4) '(1 2))((3 1) (3 2) (4 1) (4 2))CL-USER> (cartesian-product '(1 2) '())NILCL-USER> (cartesian-product '() '(1 2))NIL `

Extra credit:

`(defun n-cartesian-product (l)  "Compute the n-cartesian product of a list of sets (each of them represented as list).   Algorithm:     If there are no sets, then produce an empty set of tuples;     otherwise, for all the elements x of the first set, concatenate the sets obtained by     inserting x at the beginning of each tuple of the n-cartesian product of the remaining sets."  (if (null l)      (list nil)      (loop for x in (car l)            nconc (loop for y in (n-cartesian-product (cdr l))                          collect (cons x y)))))`

Output:

`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))CL-USER> (n-cartesian-product '((1 2 3) (30) (500 100)))((1 30 500) (1 30 100) (2 30 500) (2 30 100) (3 30 500) (3 30 100))CL-USER> (n-cartesian-product '((1 2 3) () (500 100)))NIL `

## Crystal

The first function is the basic task. The version overloaded for one argument is the extra credit task, implemented using recursion.

`def cartesian_product(a, b)    return a.flat_map { |i| b.map { |j| [i, j] } }end  def cartesian_product(l)    if l.size <= 1        return l    elsif l.size == 2        return cartesian_product(l[0], l[1])    end     return l[0].flat_map { |i|         cartesian_product(l[1..]).map { |j|            [i, j].flatten        }    }end  tests = [ [[1, 2], [3, 4]],          [[3, 4], [1, 2]],          [[1, 2], [] of Int32],          [[] of Int32, [1, 2]],          [[1, 2, 3], [30], [500, 100]],          [[1, 2, 3], [] of Int32, [500, 100]],          [[1776, 1789], [7, 12], [4, 14, 23], [0, 1]] ] tests.each { |test|    puts "#{test.join(" x ")} ->"    puts "    #{cartesian_product(test)}"    puts ""} `
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, 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] ->
[]

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

## D

`import std.stdio; void main() {    auto a = listProduct([1,2], [3,4]);    writeln(a);     auto b = listProduct([3,4], [1,2]);    writeln(b);     auto c = listProduct([1,2], []);    writeln(c);     auto d = listProduct([], [1,2]);    writeln(d);} auto listProduct(T)(T[] ta, T[] tb) {    struct Result {        int i, j;         bool empty() {            return i>=ta.length                || j>=tb.length;        }         T[] front() {            return [ta[i], tb[j]];        }         void popFront() {            if (++j>=tb.length) {                j=0;                i++;            }        }    }     return Result();}`
Output:
```[[1, 3], [1, 4], [2, 3], [2, 4]]
[[3, 1], [3, 2], [4, 1], [4, 2]]
[]
[]```

## Delphi

Translation of: Go
` program Cartesian_product_of_two_or_more_lists; {\$APPTYPE CONSOLE} uses  System.SysUtils; type  TList = TArray<Integer>;   TLists = TArray<TList>;   TListHelper = record helper for TList    function ToString: string;  end;   TListsHelper = record helper for TLists    function ToString(BreakLines: boolean = false): string;  end; function cartN(arg: TLists): TLists;var  b, n: TList;  argc: Integer;begin  argc := length(arg);   var c := 1;  for var a in arg do    c := c * length(a);   if c = 0 then    exit;   SetLength(result, c);  SetLength(b, c * argc);  SetLength(n, argc);   var s := 0;  for var i := 0 to c - 1 do  begin    var e := s + argc;    var Resi := copy(b, s, e - s);    Result[i] := Resi;     s := e;    for var j := 0 to high(n) do    begin      var nj := n[j];      Resi[j] := arg[j, nj];    end;     for var j := high(n) downto 0 do    begin      inc(n[j]);      if n[j] < Length(arg[j]) then        Break;      n[j] := 0;    end;  end;end; { TListHelper } function TListHelper.ToString: string;begin  Result := '[';  for var i := 0 to High(self) do  begin    Result := Result + self[i].ToString;    if i < High(self) then      Result := Result + ' ';  end;  Result := Result + ']';end; { TListsHelper } function TListsHelper.ToString(BreakLines: boolean = false): string;begin  Result := '[';  for var i := 0 to High(self) do  begin    Result := Result + self[i].ToString;    if i < High(self) then    begin      if BreakLines then        Result := Result + #10      else        Result := Result + ' ';    end;  end;  Result := Result + ']';end; begin  writeln(#10, cartN([[1, 2], [3, 4]]).ToString);  writeln(#10, cartN([[3, 4], [1, 2]]).ToString);  writeln(#10, cartN([[1, 2], []]).ToString);  writeln(#10, cartN([[], [1, 2]]).ToString);   writeln(#10, cartN([[1776, 1789], [17, 12], [4, 14, 23], [0, 1]]).ToString(True));   writeln(#10, cartN([[1, 2, 3], [30], [500, 100]]).ToString);   writeln(#10, cartN([[1, 2, 3], [], [500, 100]]).ToString);   {\$IFNDEF UNIX} readln; {\$ENDIF}end.`
Output:
```[[1 3] [1 4] [2 3] [2 4]]

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

[]

[]

[[1776 17 4 0]
[1776 17 4 1]
[1776 17 14 0]
[1776 17 14 1]
[1776 17 23 0]
[1776 17 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 17 4 0]
[1789 17 4 1]
[1789 17 14 0]
[1789 17 14 1]
[1789 17 23 0]
[1789 17 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]]

[]```

## F#

` //Nigel Galloway February 12th., 2018let cP2 n g = List.map (fun (n,g)->[n;g]) (List.allPairs n g) `
Output:
```cP2 [1;2] [3;4] -> [[1; 3]; [1; 4]; [2; 3]; [2; 4]]
cP2 [3;4] [1;2] -> [[3; 1]; [3; 2]; [4; 1]; [4; 2]]
cP2 [1;2] []    -> []
cP2 [] [1;2]    -> []
```

### Extra Credit

` //Nigel Galloway August 14th., 2018let cP ng=Seq.foldBack(fun n g->[for n' in n do for g' in g do yield n'::g']) ng [[]] `
Output:
```cP [[1;2];[3;4]] -> [[1; 3]; [1; 4]; [2; 3]; [2; 4]]
cP [[3;4];[1;2]] -> [[3; 1]; [3; 2]; [4; 1]; [4; 2]]
cP [[3;4];[]] ->[]
cP [[];[1;2]] ->[]
cP [[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]]
cP [[1;2;3];[30];[500;100]] -> [[1; 30; 500]; [1; 30; 100]; [2; 30; 500]; [2; 30; 100]; [3; 30; 500]; [3; 30; 100]]
cP [[1;2;3];[];[500;100]] -> []
```

## Factor

`IN: scratchpad { 1 2 } { 3 4 } cartesian-product .{ { { 1 3 } { 1 4 } } { { 2 3 } { 2 4 } } }IN: scratchpad { 3 4 } { 1 2 } cartesian-product .{ { { 3 1 } { 3 2 } } { { 4 1 } { 4 2 } } }IN: scratchpad { 1 2 } { } cartesian-product .{ { } { } }IN: scratchpad { } { 1 2 } cartesian-product .{ }`

## FreeBASIC

I'll leave the extra credit part for someone else. It's just going to amount to repeatedly finding Cartesian products and flattening the result, so considerably less interesting than Cartesian products where the list items themselves can be lists.

`#define MAXLEN 64 type listitem                  ' An item of a list may be a number    is_num as boolean       ' or another list, so I have to account    union                      ' for both, implemented as a union.        list as any ptr        ' FreeBASIC is twitchy about circularly        num as uinteger        ' defined types, so one workaround is to    end union                  ' use a generic pointer that I will castend type                       ' later. type list    length as uinteger              'simple, fixed storage length lists    item(1 to MAXLEN) as listitem   'are good enough for this exampleend type sub print_list( list as list )    print "{";    if list.length = 0 then print "}"; : return    for i as uinteger = 1 to list.length        if list.item(i).is_num then            print str(list.item(i).num);        else     'recursively print sublist            print_list( *cast(list ptr, list.item(i).list) )        end if    if i<list.length then print ", "; else print "}";   'handle comma    next i                                              'gracefully    returnend sub function cartprod( A as list, B as list ) as list    dim as uinteger i, j    dim as list C    dim as list ptr inner  'for brevity    C.length = 0    for i = 1 to A.length        for j = 1 to B.length            C.length += 1            C.item(C.length).is_num = false   'each item of the new list is a list itself            inner = allocate( sizeof(list) )     'make space for it            C.item(C.length).list = inner            inner->length = 2                    'each inner list contains two items            inner->item(1) = A.item(i)           'one from the first list            inner->item(2) = B.item(j)           'and one from the second        next j    next i    return Cend function dim as list EMPTY, A, B, REMPTY.length = 0A.length = 2 A.item(1).is_num = true : A.item(1).num = 1A.item(2).is_num = true : A.item(2).num = 2B.length = 2 B.item(1).is_num = true : B.item(1).num = 3B.item(2).is_num = true : B.item(2).num = 4 R = cartprod(A, B)print_list(R) : print   'print_list does not supply a final newlineR = cartprod(B, A) : print_list(R) : printR = cartprod(A, EMPTY) : print_list(R) : printR = cartprod(EMPTY, A) : print_list(R) : print`
Output:
```{{1, 3}, {1, 4}, {2, 3}, {2, 4}}
{{3, 1}, {3, 2}, {4, 1}, {4, 2}}
{}
{}

```

## Fortran

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.

`  ! Created by simon on 29/04/2021.  ! ifort -o cartesian_product cartesian_product.f90 -check all  module tuple    implicit none    private    public :: tuple_t, operator(*), print     type tuple_t(n)        integer, len     :: n        integer, private :: v(n)    contains        procedure, public :: print => print_tuple_t        generic, public :: assignment(=) => eq_tuple_t        procedure, public :: eq_tuple_t    end type tuple_t     interface print        module procedure print_tuple_a_t    end interface print    interface operator(*)        module procedure tup_times_tup    end interface  contains    subroutine eq_tuple_t(this, src)        class(tuple_t(*)), intent(inout) :: this        integer, intent(in)              :: src(:)        this%v = src    end subroutine eq_tuple_t     pure function tup_times_tup(a, b) result(r)        type(tuple_t(*)), intent(in)  :: a        type(tuple_t(*)), intent(in)  :: b        type(tuple_t(2)), allocatable :: r(:)        integer :: i, j, k         allocate(r(a%n*b%n))        k = 0        do i=1,a%n            do j=1,b%n                k = k + 1                r(k)%v = [a%v(i),b%v(j)]            end do        end do    end function tup_times_tup     subroutine print_tuple_t(this)        class(tuple_t(*)), intent(in) :: this        integer :: i        write(*,fmt='(a)',advance='no') '{'        do i=1,size(this%v)            write(*,fmt='(i0)',advance='no') this%v(i)            if (i < size(this%v)) write(*,fmt='(a)',advance='no') ','        end do        write(*,fmt='(a)',advance='no') '}'    end subroutine print_tuple_t     subroutine print_tuple_a_t(r)        type(tuple_t(*)), intent(in) :: r(:)        integer :: i        write(*,fmt='(a)',advance='no') '{'        do i=1,size(r)            call r(i)%print            if (i < size(r)) write(*,fmt='(a)',advance='no') ','        end do        write(*,fmt='(a)') '}'    end subroutine print_tuple_a_t end module tuple  program cartesian_product    use tuple     implicit none    type(tuple_t(2)) :: a, b    type(tuple_t(0)) :: z     a = [1,2]    b = [3,4]     call print_product(a, b)    call print_product(b, a)    call print_product(z, a)    call print_product(a, z)     stop contains    subroutine print_product(s, t)        type(tuple_t(*)), intent(in) :: s        type(tuple_t(*)), intent(in) :: t        call s%print        write(*,fmt='(a)',advance='no') ' x '        call t%print        write(*,fmt='(a)',advance='no') ' = '        call print(s*t)    end subroutine print_product end program cartesian_product `

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} = {}
```

## Go

`package main import "fmt" type pair [2]int func cart2(a, b []int) []pair {    p := make([]pair, len(a)*len(b))    i := 0    for _, a := range a {        for _, b := range b {            p[i] = pair{a, b}            i++        }    }    return p} func main() {    fmt.Println(cart2([]int{1, 2}, []int{3, 4}))    fmt.Println(cart2([]int{3, 4}, []int{1, 2}))    fmt.Println(cart2([]int{1, 2}, nil))    fmt.Println(cart2(nil, []int{1, 2}))}`
Output:
```[[1 3] [1 4] [2 3] [2 4]]
[[3 1] [3 2] [4 1] [4 2]]
[]
[]
```

Extra credit 1

This solution minimizes allocations and computes and fills the result sequentially.

`package main import "fmt" func cartN(a ...[]int) [][]int {    c := 1    for _, a := range a {        c *= len(a)    }    if c == 0 {        return nil    }    p := make([][]int, c)    b := make([]int, c*len(a))    n := make([]int, len(a))    s := 0    for i := range p {        e := s + len(a)        pi := b[s:e]        p[i] = pi        s = e        for j, n := range n {            pi[j] = a[j][n]        }        for j := len(n) - 1; j >= 0; j-- {            n[j]++            if n[j] < len(a[j]) {                break            }            n[j] = 0        }    }    return p} func main() {    fmt.Println(cartN([]int{1, 2}, []int{3, 4}))    fmt.Println(cartN([]int{3, 4}, []int{1, 2}))    fmt.Println(cartN([]int{1, 2}, nil))    fmt.Println(cartN(nil, []int{1, 2}))     fmt.Println()    fmt.Println("[")    for _, p := range cartN(        []int{1776, 1789},        []int{7, 12},        []int{4, 14, 23},        []int{0, 1},    ) {        fmt.Println(" ", p)    }    fmt.Println("]")    fmt.Println(cartN([]int{1, 2, 3}, []int{30}, []int{500, 100}))    fmt.Println(cartN([]int{1, 2, 3}, []int{}, []int{500, 100}))     fmt.Println()    fmt.Println(cartN(nil))    fmt.Println(cartN())}`
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]]
[]

[]
[[]]
```

Extra credit 2

Code here is more compact, but with the cost of more garbage produced. It produces the same result as cartN above.

`func cartN(a ...[]int) (c [][]int) {    if len(a) == 0 {        return [][]int{nil}    }    r := cartN(a[1:]...)    for _, e := range a[0] {        for _, p := range r {            c = append(c, append([]int{e}, p...))        }    }    return}`

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.

`func cartN(a ...[]int) (c [][]int) {    if len(a) == 0 {        return [][]int{nil}    }    last := len(a) - 1    l := cartN(a[:last]...)    for _, e := range a[last] {        for _, p := range l {            c = append(c, append(p, e))        }    }    return}`

## Groovy

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

`class CartesianCategory {    static Iterable multiply(Iterable a, Iterable b) {        assert [a,b].every { it != null }        def (m,n) = [a.size(),b.size()]        (0..<(m*n)).inject([]) { prod, i -> prod << [a[i.intdiv(n)], b[i%n]].flatten() }    }}`

Test:
The mixin method call is necessary to make the multiply (*) operator work.

`Iterable.metaClass.mixin CartesianCategory println "\nCore Solution:"println "[1, 2] × [3, 4] = \${[1, 2] * [3, 4]}"println "[3, 4] × [1, 2] = \${[3, 4] * [1, 2]}"println "[1, 2] × [] = \${[1, 2] * []}"println "[] × [1, 2] = \${[] * [1, 2]}" println "\nExtra Credit:"println "[1776, 1789] × [7, 12] × [4, 14, 23] × [0, 1] = \${[1776, 1789] * [7, 12] * [4, 14, 23] * [0, 1]}"println "[1, 2, 3] × [30] × [500, 100] = \${[1, 2, 3] * [30] * [500, 100]}"println "[1, 2, 3] × [] × [500, 100] = \${[1, 2, 3] * [] * [500, 100]}" println "\nNon-Numeric Example:"println "[John,Paul,George,Ringo] × [Emerson,Lake,Palmer] × [Simon,Garfunkle] = ["( ["John","Paul","George","Ringo"] * ["Emerson","Lake","Palmer"] * ["Simon","Garfunkle"] ).each { println "\t\${it}," }println "]"`

Output:

```Core Solution:
[1, 2] × [3, 4] = [[1, 3], [1, 4], [2, 3], [2, 4]]
[3, 4] × [1, 2] = [[3, 1], [3, 2], [4, 1], [4, 2]]
[1, 2] × [] = []
[] × [1, 2] = []

Extra Credit:
[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]]
[1, 2, 3] × [30] × [500, 100] = [[1, 30, 500], [1, 30, 100], [2, 30, 500], [2, 30, 100], [3, 30, 500], [3, 30, 100]]
[1, 2, 3] × [] × [500, 100] = []

Non-Numeric Example:
[John,Paul,George,Ringo] × [Emerson,Lake,Palmer] × [Simon,Garfunkle] = [
[John, Emerson, Simon],
[John, Emerson, Garfunkle],
[John, Lake, Simon],
[John, Lake, Garfunkle],
[John, Palmer, Simon],
[John, Palmer, Garfunkle],
[Paul, Emerson, Simon],
[Paul, Emerson, Garfunkle],
[Paul, Lake, Simon],
[Paul, Lake, Garfunkle],
[Paul, Palmer, Simon],
[Paul, Palmer, Garfunkle],
[George, Emerson, Simon],
[George, Emerson, Garfunkle],
[George, Lake, Simon],
[George, Lake, Garfunkle],
[George, Palmer, Simon],
[George, Palmer, Garfunkle],
[Ringo, Emerson, Simon],
[Ringo, Emerson, Garfunkle],
[Ringo, Lake, Simon],
[Ringo, Lake, Garfunkle],
[Ringo, Palmer, Simon],
[Ringo, Palmer, Garfunkle],
]```

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 >>= (<\$> as) . (:)) [[]]`

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

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 0  │1776 7 4 1  │├────────────┼────────────┤│1776 7 14 0 │1776 7 14 1 │├────────────┼────────────┤│1776 7 23 0 │1776 7 23 1 │└────────────┴────────────┘ ┌────────────┬────────────┐│1776 12 4 0 │1776 12 4 1 │├────────────┼────────────┤│1776 12 14 0│1776 12 14 1│├────────────┼────────────┤│1776 12 23 0│1776 12 23 1│└────────────┴────────────┘  ┌────────────┬────────────┐│1789 7 4 0  │1789 7 4 1  │├────────────┼────────────┤│1789 7 14 0 │1789 7 14 1 │├────────────┼────────────┤│1789 7 23 0 │1789 7 23 1 │└────────────┴────────────┘ ┌────────────┬────────────┐│1789 12 4 0 │1789 12 4 1 │├────────────┼────────────┤│1789 12 14 0│1789 12 14 1│├────────────┼────────────┤│1789 12 23 0│1789 12 23 1│└────────────┴────────────┘   { 1 2 3 ; 30 ; 50 100    NB. result is a 2-dimensional array with shape 2 3┌───────┬────────┐│1 30 50│1 30 100│├───────┼────────┤│2 30 50│2 30 100│├───────┼────────┤│3 30 50│3 30 100│└───────┴────────┘   { 1 2 3 ; '' ; 50 100    NB. result is an empty 3-dimensional array with shape 3 0 2 `

## Java

Works with: Java Virtual Machine version 1.8
` import static java.util.Arrays.asList;import static java.util.Collections.emptyList;import static java.util.Optional.of;import static java.util.stream.Collectors.toList; import java.util.List; public class CartesianProduct {     public List<?> product(List<?>... a) {        if (a.length >= 2) {            List<?> product = a[0];            for (int i = 1; i < a.length; i++) {                product = product(product, a[i]);            }            return product;        }         return emptyList();    }     private <A, B> List<?> product(List<A> a, List<B> b) {        return of(a.stream()                .map(e1 -> of(b.stream().map(e2 -> asList(e1, e2)).collect(toList())).orElse(emptyList()))                .flatMap(List::stream)                .collect(toList())).orElse(emptyList());    }} `

Using a generic class with a recursive function

` import java.util.ArrayList;import java.util.Arrays;import java.util.List; public class CartesianProduct<V> { 	public List<List<V>> product(List<List<V>> lists) {		List<List<V>> product = new ArrayList<>(); 		// We first create a list for each value of the first list		product(product, new ArrayList<>(), lists); 		return product;	} 	private void product(List<List<V>> result, List<V> existingTupleToComplete, List<List<V>> valuesToUse) {		for (V value : valuesToUse.get(0)) {			List<V> newExisting = new ArrayList<>(existingTupleToComplete);			newExisting.add(value); 			// If only one column is left			if (valuesToUse.size() == 1) {				// We create a new list with the exiting tuple for each value with the value				// added				result.add(newExisting);			} else {				// If there are still several columns, we go into recursion for each value				List<List<V>> newValues = new ArrayList<>();				// We build the next level of values				for (int i = 1; i < valuesToUse.size(); i++) {					newValues.add(valuesToUse.get(i));				} 				product(result, newExisting, newValues);			}		}	} 	public static void main(String[] args) {		List<Integer> list1 = new ArrayList<>(Arrays.asList(new Integer[] { 1776, 1789 }));		List<Integer> list2 = new ArrayList<>(Arrays.asList(new Integer[] { 7, 12 }));		List<Integer> list3 = new ArrayList<>(Arrays.asList(new Integer[] { 4, 14, 23 }));		List<Integer> list4 = new ArrayList<>(Arrays.asList(new Integer[] { 0, 1 })); 		List<List<Integer>> input = new ArrayList<>();		input.add(list1);		input.add(list2);		input.add(list3);		input.add(list4); 		CartesianProduct<Integer> cartesianProduct = new CartesianProduct<>();		List<List<Integer>> product = cartesianProduct.product(input);		System.out.println(product);	}} `

## JavaScript

### ES6

#### Functional

Cartesian products fall quite naturally out of concatMap (Array.flatMap), 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 =>        xs.flatMap(x => ys.map(y => [x, y]))      // TEST -----------------------------------------------    return [        cartProd([1, 2])([3, 4]),        cartProd([3, 4])([1, 2]),        cartProd([1, 2])([]),        cartProd([])([1, 2]),    ].map(JSON.stringify).join('\n');})();`
Output:
```[[1,3],[1,4],[2,3],[2,4]]
[[3,1],[3,2],[4,1],[4,2]]
[]
[]```

Abstracting a little more, we can define the cartesian product quite economically in terms of a general applicative operator:

`(() => {     // CARTESIAN PRODUCT OF TWO LISTS ---------------------     // cartesianProduct :: [a] -> [b] -> [(a, b)]    const cartesianProduct = xs =>        ap(xs.map(Tuple));      // GENERIC FUNCTIONS ----------------------------------     // e.g. [(*2),(/2), sqrt] <*> [1,2,3]    // -->  ap([dbl, hlf, root], [1, 2, 3])    // -->  [2,4,6,0.5,1,1.5,1,1.4142135623730951,1.7320508075688772]     // Each member of a list of functions applied to each    // of a list of arguments, deriving a list of new values.     // ap (<*>) :: [(a -> b)] -> [a] -> [b]    const ap = fs => xs =>        // The sequential application of each of a list        // of functions to each of a list of values.        fs.flatMap(            f => xs.map(f)        );     // Tuple (,) :: a -> b -> (a, b)    const Tuple = a => b => [a, b];     // TEST -----------------------------------------------    return [            cartesianProduct([1, 2])([3, 4]),            cartesianProduct([3, 4])([1, 2]),            cartesianProduct([1, 2])([]),            cartesianProduct([])([1, 2]),        ]        .map(JSON.stringify)        .join('\n');})();`
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:

`(() => {    const main = () => {        // n-ary Cartesian product of a list of lists.         // cartProdN :: [[a]] -> [[a]]        const cartProdN = foldr(            xs => as =>            bind(as)(                x => bind(xs)(                    a => [                        [a].concat(x)                    ]                )            )        )([            []        ]);         // TEST -------------------------------------------        return intercalate('\n\n')([            map(show)(                cartProdN([                    [1776, 1789],                    [7, 12],                    [4, 14, 23],                    [0, 1]                ])            ).join('\n'),            show(cartProdN([                [1, 2, 3],                [30],                [50, 100]            ])),            show(cartProdN([                [1, 2, 3],                [],                [50, 100]            ]))        ])    };     // GENERIC FUNCTIONS ----------------------------------     // bind ::  [a] -> (a -> [b]) -> [b]    const bind = xs => f => xs.flatMap(f);     // foldr :: (a -> b -> b) -> b -> [a] -> b    const foldr = f => a => xs =>        xs.reduceRight((a, x) => f(x)(a), 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);     return main();})();`
Output:
```[1776,7,4,0]
[1776,7,4,1]
[1776,7,14,0]
[1776,7,14,1]
[1776,7,23,0]
[1776,7,23,1]
[1776,12,4,0]
[1776,12,4,1]
[1776,12,14,0]
[1776,12,14,1]
[1776,12,23,0]
[1776,12,23,1]
[1789,7,4,0]
[1789,7,4,1]
[1789,7,14,0]
[1789,7,14,1]
[1789,7,23,0]
[1789,7,23,1]
[1789,12,4,0]
[1789,12,4,1]
[1789,12,14,0]
[1789,12,14,1]
[1789,12,23,0]
[1789,12,23,1]

[[1,30,50],[1,30,100],[2,30,50],[2,30,100],[3,30,50],[3,30,100]]

[]```

#### Imperative

Imperative implementations of Cartesian products are inevitably less compact and direct, but we can certainly write an iterative translation of a fold over nested applications of bind or concatMap:

`(() => {    // 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

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

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

Run in REPL.

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

## Kotlin

`// 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]
]
```

## langur

We could use mapX() to map each set of values to a function, but this assignment only requires an array of arrays, so we use the X() function.

Works with: langur version 0.8.3
`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([1, 2], []) == []writeln X([], [1, 2]) == []writeln() writeln X [1776, 1789], [7, 12], [4, 14, 23], [0, 1]writeln() writeln X [1, 2, 3], [30], [500, 100]writeln() writeln X [1, 2, 3], [], [500, 100]writeln()`
Output:
```true
true
true
true

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

[]
```

## Lua

### Functional

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

### Using coroutines

I have not benchmarked this, but I believe that this should run faster than the functional implementation and also likely the imperative implementation, it has significantly fewer function calls per iteration, and only the stack changes during iteration (no garbage collection during iteration). On the other hand due to avoiding garbage collection, result is reused between returns, so mutating the returned result is unsafe.

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.

`local function cartesian_product(sets)  local result = {}  local set_count = #sets--[[ I believe that this should make the below go very slightly faster, because it doesn't need to lookup yield in coroutine each time it     yields, though perhaps the compiler optimises the lookup away? ]]  local yield = coroutine.yield   local function descend(depth)    if depth == set_count then      for k,v in pairs(sets[depth]) do        result[depth] = v        yield(result)      end    else      for k,v in pairs(sets[depth]) do        result[depth] = v        descend(depth + 1)      end    end  end  return coroutine.wrap(function() descend(1) end)end --- testslocal test_cases = {  {{1, 2}, {3, 4}},  {{3, 4}, {1, 2}},  {{1776, 1789}, {7, 12}, {4, 14, 23}, {0,1}},  {{1,2,3}, {30}, {500, 100}},  {{1,2,3}, {}, {500, 100}}} local function format_nested_list(list)  if list[1] and type(list[1]) == "table" then    local formatted_items = {}    for i, item in ipairs(list) do      formatted_items[i] = format_nested_list(item)    end    return format_nested_list(formatted_items)  else    return "{" .. table.concat(list, ",") .. "}"  endend for _,test_case in ipairs(test_cases) do  print(format_nested_list(test_case))  for product in cartesian_product(test_case) do    print("  " .. format_nested_list(product))  endend`

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

`local function cartesian_product(sets)  local item_counts = {}  local indices = {}  local results = {}  local set_count = #sets  local combination_count = 1   for set_index=set_count, 1, -1 do    local set = sets[set_index]    local item_count = #set    item_counts[set_index] = item_count    indices[set_index] = 1    results[set_index] = set[1]    combination_count = combination_count * item_count  end   local combination_index = 0   return function()    if combination_index >= combination_count then return end -- no more output     if combination_index == 0 then goto skip_update end -- skip first index update     indices[set_count] = indices[set_count] + 1     for set_index=set_count, 1, -1 do -- update index list      local set = sets[set_index]      local index = indices[set_index]      if index <= item_counts[set_index] then        results[set_index] = set[index]        break -- no further update needed      else -- propagate item_counts overflow        results[set_index] = set[1]        indices[set_index] = 1        if set_index > 1 then          indices[set_index - 1] = indices[set_index - 1] + 1        end      end    end     ::skip_update::     combination_index = combination_index + 1     return combination_index, results  endend--- testslocal test_cases = {  {{1, 2}, {3, 4}},  {{3, 4}, {1, 2}},  {{1776, 1789}, {7, 12}, {4, 14, 23}, {0,1}},  {{1,2,3}, {30}, {500, 100}},  {{1,2,3}, {}, {500, 100}}} local function format_nested_list(list)  if list[1] and type(list[1]) == "table" then    local formatted_items = {}    for i, item in ipairs(list) do      formatted_items[i] = format_nested_list(item)    end    return format_nested_list(formatted_items)  else    return "{" .. table.concat(list, ",") .. "}"  endend for _,test_case in ipairs(test_cases) do  print(format_nested_list(test_case))  for i, product in cartesian_product(test_case) do    print(i, format_nested_list(product))  endend`

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

`-- support:function T(t) return setmetatable(t, {__index=table}) endtable.clone = function(t) local s=T{} for k,v in ipairs(t) do s[k]=v end return s endtable.reduce = function(t,f,acc) for i=1,#t do acc=f(t[i],acc) end return acc end -- implementation:local function cartprod(sets)  local temp, prod = T{}, T{}  local function descend(depth)    for _,v in ipairs(sets[depth]) do      temp[depth] = v      if (depth==#sets) then prod[#prod+1]=temp:clone() else descend(depth+1) end    end  end  descend(1)  return prodend -- demonstration:tests = {  { {1, 2}, {3, 4} },  { {3, 4}, {1, 2} },  { {1, 2}, {} },  { {}, {1, 2} },  { {1776, 1789}, {7, 12}, {4, 14, 23}, {0, 1} },  { {1, 2, 3}, {30}, {500, 100} },  { {1, 2, 3}, {}, {500, 100} }}for _,test in ipairs(tests) do  local cp = cartprod(test)  print("{"..cp:reduce(function(t,a) return (a=="" and a or a..", ").."("..t:concat(", ")..")" end,"").."}")end`
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)}
{}```

## Maple

` 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; `

## Mathematica/Wolfram Language

`cartesianProduct[args__] := Flatten[Outer[List, args], Length[{args}] - 1]`

## Modula-2

`MODULE CartesianProduct;FROM FormatString IMPORT FormatString;FROM Terminal IMPORT WriteString,WriteLn,ReadChar; PROCEDURE WriteInt(a : INTEGER);VAR buf : ARRAY[0..9] OF CHAR;BEGIN    FormatString("%i", buf, a);    WriteString(buf)END WriteInt; PROCEDURE Cartesian(a,b : ARRAY OF INTEGER);VAR i,j : CARDINAL;BEGIN    WriteString("[");    FOR i:=0 TO HIGH(a) DO        FOR j:=0 TO HIGH(b) DO            IF (i>0) OR (j>0) THEN                WriteString(",");            END;            WriteString("[");            WriteInt(a[i]);            WriteString(",");            WriteInt(b[j]);            WriteString("]")        END    END;    WriteString("]");    WriteLnEND Cartesian; TYPE    AP = ARRAY[0..1] OF INTEGER;    E = ARRAY[0..0] OF INTEGER;VAR    a,b : AP;BEGIN    a := AP{1,2};    b := AP{3,4};    Cartesian(a,b);     a := AP{3,4};    b := AP{1,2};    Cartesian(a,b);     (* If there is a way to create an empty array, I do not know of it *)     ReadCharEND CartesianProduct.`

## Nim

### Task: product of two lists

To compute the product of two lists (Nim arrays or sequences), we use an iterator. Obtaining a sequence from an iterator is easily done using "toSeq" from the module “sequtils” of the standard library.

The procedure allows to mix sequences of different types, for instance integers and characters.

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.

`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 tuples rather than arrays as it allows T1 and T2 to be different.   for x in a:    for y in b:      yield (x, y) #——————————————————————————————————————————————————————————————————————————————————————————————————— when isMainModule:   from seqUtils import toSeq  import strformat  from strutils import addSep   #-------------------------------------------------------------------------------------------------   proc `\$`[T1, T2](t: tuple[a: T1, b: T2]): string =    ## Overloading of `\$` to display a tuple without the field names.    &"({t.a}, {t.b})"   proc `\$\$`[T](s: seq[T]): string =    ## New operator to display a sequence using mathematical set notation.    result = "{"    for item in s:      result.addSep(", ", 1)      result.add(\$item)    result.add('}') #-------------------------------------------------------------------------------------------------   const Empty = newSeq[int]()   # Empty list of "int".   for (a, b) in [(@[1, 2], @[3, 4]),                 (@[3, 4], @[1, 2]),                 (@[1, 2],  Empty ),                 ( Empty,  @[1, 2])]:     echo &"{\$\$a} x {\$\$b} = {\$\$toSeq(product(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} = {}```

### Extra credit: product of n list

#### Recursive procedure

As iterators cannot be recursive, we have to use a procedure which returns the whole sequence. And as we don’t know the number of sequences, we use a “varargs”. So all the sequences must contain the same type of values, values which are returned as sequences and not tuples.

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.

`proc product[T](a: varargs[seq[T]]): seq[seq[T]] =  ## Return the product of several sets (sequences).   if a.len == 1:    for x in a[0]:      result.add(@[x])  else:    for x in a[0]:      for s in product(a[1..^1]):        result.add(x & s) #——————————————————————————————————————————————————————————————————————————————————————————————————— when isMainModule:   import strformat   let    a = @[1, 2]    b = @[3, 4]    c = @[5, 6]  echo &"{a} x {b} x {c} = {product(a, b, c)}"`
Output:
`@[1, 2] x @[3, 4] x @[5, 6] = @[@[1, 3, 5], @[1, 3, 6], @[1, 4, 5], @[1, 4, 6], @[2, 3, 5], @[2, 3, 6], @[2, 4, 5], @[2, 4, 6]]`

#### Using a macro

Another way to compute the product consists to use a macro. It would be possible to create an iterator but it’s somewhat easier to produce the code to build the whole sequence. No recursion here: we generate nested loops, so the algorithm is the simplest possible.

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.

`import macros macro product(args: varargs[typed]): untyped =  ## Macro to generate the code to build the product of several sequences.   let t = args[0].getType()  if t.kind != nnkBracketExpr or t[0].kind != nnkSym or \$t[0] != "seq":    error("Arguments must be sequences", args)   # Build the result type i.e. a tuple with "args.len" elements.  # Fields are named "f0", "f1", etc.  let tupleTyNode = newNimNode(nnkTupleTy)  for idx, arg in args:    let identDefsNode = newIdentDefs(ident('f' & \$idx), arg.getType()[1])    tupleTyNode.add(identDefsNode)   # Build the nested for loops with counter "i0", "i1", etc.  var stmtListNode = newStmtList()  let loopsNode = nnkForStmt.newTree(ident("i0"), ident(\$args[0]), stmtListNode)  var idx = 0  for arg in args[1..^1]:    inc idx    let loopNode = nnkForStmt.newTree(ident('i' & \$idx), ident(\$arg))    stmtListNode.add(loopNode)    stmtListNode = newStmtList()    loopNode.add(stmtListNode)   # Build the instruction "result.add(i1, i2,...)".  let parNode = newPar()  let addNode = newCall(newDotExpr(ident("result"), ident("add")), parNode)  for i, arg in args:    parNode.add(ident('i' & \$i))  stmtListNode.add(addNode)   # Build the tree.  result = nnkStmtListExpr.newTree(             nnkVarSection.newTree(               newIdentDefs(                 ident("result"),                 nnkBracketExpr.newTree(ident("seq"), tupleTyNode))),               loopsNode,             ident("result")) #——————————————————————————————————————————————————————————————————————————————————————————————————— when isMainModule:   import strformat  import strutils   #-------------------------------------------------------------------------------------------------   proc `\$`[T: tuple](t: T): string =    ## Overloading of `\$` to display a tuple without the field names.    result = "("    for f in t.fields:      result.addSep(", ", 1)      result.add(\$f)    result.add(']')   proc `\$\$`[T](s: seq[T]): string =    ## New operator to display a sequence using mathematical set notation.    result = "{"    for item in s:      result.addSep(", ", 1)      result.add(\$item)    result.add('}')   #-------------------------------------------------------------------------------------------------   var a = @[1, 2]  var b = @['a', 'b']  var c = @[false, true]  echo &"{\$\$a} x {\$\$b} x {\$\$c} = {\$\$product(a, b, c)}"`
Output:
`{1, 2} x {a, b} x {false, true} = {(1, a, false], (1, a, true], (1, b, false], (1, b, true], (2, a, false], (2, a, true], (2, b, false], (2, b, true]}`

## OCaml

The double semicolons are necessary only for the toplevel

`let rec product l1 l2 =     match l1, l2 with    | [], _ | _, [] -> []    | h1::t1, h2::t2 -> (h1,h2)::(product [h1] t2)@(product t1 l2);; product [1;2] [3;4];;(*- : (int * int) list = [(1, 3); (1, 4); (2, 3); (2, 4)]*)product [3;4] [1;2];;(*- : (int * int) list = [(3, 1); (3, 2); (4, 1); (4, 2)]*)product [1;2] [];;(*- : (int * 'a) list = []*)product [] [1;2];;(*- : ('a * int) list = []*)`

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.

`let product' l1 l2 =     let rec aux ~acc l1' l2' =         match l1', l2' with        | [], _ | _, [] -> acc        | h1::t1, h2::t2 ->             let acc = (h1,h2)::acc in            let acc = aux ~acc t1 l2' in            aux ~acc [h1] t2    in aux [] l1 l2;; product' [1;2] [3;4];;(*- : (int * int) list = [(1, 4); (2, 4); (2, 3); (1, 3)]*)product' [3;4] [1;2];;(*- : (int * int) list = [(3, 2); (4, 2); (4, 1); (3, 1)]*)product' [1;2] [];;(*- : (int * 'a) list = []*)product' [] [1;2];;(*- : ('a * int) list = []*)`

Implemented using nested folds:

`let cart_prod l1 l2 =  List.fold_left (fun acc1 ele1 ->    List.fold_left (fun acc2 ele2 -> (ele1,ele2)::acc2) acc1 l2) [] l1 ;; cart_prod [1; 2; 3] ['a'; 'b'; 'c'] ;;(*- : (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] [] ;;(*- : ('a * int) list = [] *)`

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.

`let rec product'' l =     (* We need to do the cross product of our current list and all the others     * so we define a helper function for that *)    let rec aux ~acc l1 l2 = match l1, l2 with    | [], _ | _, [] -> acc    | h1::t1, h2::t2 ->         let acc = (h1::h2)::acc in        let acc = (aux ~acc t1 l2) in        aux ~acc [h1] t2    (* now we can do the actual computation *)    in match l with    | [] -> []    | [l1] -> List.map (fun x -> [x]) l1    | l1::tl ->        let tail_product = product'' tl in        aux ~acc:[] l1 tail_product  product'' [[1;2];[3;4]];;(*- : int list list = [[1; 4]; [2; 4]; [2; 3]; [1; 3]]*)product'' [[3;4];[1;2]];;(*- : int list list = [[3; 2]; [4; 2]; [4; 1]; [3; 1]]*)product'' [[1;2];[]];;(*- : int list list = []*)product'' [[];[1;2]];;(*- : int list list = []*)product'' [[1776; 1789];[7; 12];[4; 14; 23];[0; 1]];;(*- : int list list = [[1776; 7; 4; 1]; [1776; 12; 4; 1]; [1776; 12; 14; 1]; [1776; 12; 23; 1]; [1776; 12; 23; 0]; [1776; 12; 14; 0]; [1776; 12; 4; 0]; [1776; 7; 14; 1]; [1776; 7; 23; 1]; [1776; 7; 23; 0]; [1776; 7; 14; 0]; [1789; 7; 4; 1]; [1789; 12; 4; 1]; [1789; 12; 14; 1]; [1789; 12; 23; 1]; [1789; 12; 23; 0]; [1789; 12; 14; 0]; [1789; 12; 4; 0]; [1789; 7; 14; 1]; [1789; 7; 23; 1]; [1789; 7; 23; 0]; [1789; 7; 14; 0]; [1789; 7; 4; 0]; [1776; 7; 4; 0]]*)product'' [[1; 2; 3];[30];[500; 100]];;(*- : int list list = [[1; 30; 500]; [2; 30; 500]; [3; 30; 500]; [3; 30; 100]; [2; 30; 100]; [1; 30; 100]]*)product'' [[1; 2; 3];[];[500; 100]];;(*- : int list list = []*)`

### Better type

In the latter example, our function has this signature:

`val product'' : 'a list list -> 'a list list = <fun>`

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:

`type 'a tuple = 'a list let rec product'' (l:'a list tuple) =    (* We need to do the cross product of our current list and all the others     * so we define a helper function for that *)    let rec aux ~acc l1 l2 = match l1, l2 with    | [], _ | _, [] -> acc    | h1::t1, h2::t2 ->        let acc = (h1::h2)::acc in        let acc = (aux ~acc t1 l2) in        aux ~acc [h1] t2    (* now we can do the actual computation *)    in match l with    | [] -> []    | [l1] -> List.map ~f:(fun x -> ([x]:'a tuple)) l1    | l1::tl ->        let tail_product = product'' tl in        aux ~acc:[] l1 tail_product;; type 'a tuple = 'a listval product'' : 'a list tuple -> 'a tuple list = <fun>`

## Perl

#### Iterative

Nested loops, with a short-circuit to quit early if any term is an empty set.

`sub cartesian {    my \$sets = shift @_;    for (@\$sets) { return [] unless @\$_ }     my \$products = [[]];    for my \$set (reverse @\$sets) {        my \$partial = \$products;        \$products = [];        for my \$item (@\$set) {            for my \$product (@\$partial) {                push @\$products, [\$item, @\$product];            }        }    }    \$products;} sub product {    my(\$s,\$fmt) = @_;    my \$tuples;    for \$a ( @{ cartesian( \@\$s ) } ) { \$tuples .= sprintf "(\$fmt) ", @\$a; }    \$tuples . "\n";} print product([[1, 2],      [3, 4]                  ], '%1d %1d'        ).product([[3, 4],      [1, 2]                  ], '%1d %1d'        ).product([[1, 2],      []                      ], '%1d %1d'        ).product([[],          [1, 2]                  ], '%1d %1d'        ).product([[1,2,3],     [30],   [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')`
Output:
```(1 3) (1 4) (2 3) (2 4)
(3 1) (3 2) (4 1) (4 2)

(1 30 500) (1 30 100) (2 30 500) (2 30 100) (3 30 500) (3 30 100)

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

#### Glob

This being Perl, there's more than one way to do it. A quick demonstration of how `glob`, more typically used for filename wildcard expansion, can solve the task.

`\$tuples = [ map { [split /:/] } glob '{1,2,3}:{30}:{500,100}' ]; for \$a (@\$tuples) { printf "(%1d %2d %3d) ", @\$a; }`
Output:
`(1 30 500) (1 30 100) (2 30 500) (2 30 100) (3 30 500) (3 30 100)`

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

`use ntheory qw/forsetproduct/;forsetproduct { say "@_" } [1,2,3],[qw/a b c/],[qw/@ \$ !/]; use Set::Product qw/product/;product { say "@_" } [1,2,3],[qw/a b c/],[qw/@ \$ !/]; use Math::Cartesian::Product;cartesian { say "@_" } [1,2,3],[qw/a b c/],[qw/@ \$ !/]; use Algorithm::Loops qw/NestedLoops/;NestedLoops([[1,2,3],[qw/a b c/],[qw/@ \$ !/]], sub { say "@_"; });`

## Phix

```with javascript_semantics
function cart(sequence s)
sequence res = {}
for n=2 to length(s) do
for i=1 to length(s[1]) do
for j=1 to length(s[2]) do
res = append(res,s[1][i]&s[2][j])
end for
end for
if length(s)=2 then exit end if
s[1..2] = {res}
res = {}
end for
return res
end function

?cart({{1,2},{3,4}})
?cart({{3,4},{1,2}})
?cart({{1,2},{}})
?cart({{},{1,2}})
?cart({{1776, 1789},{7, 12},{4, 14, 23},{0, 1}})
?cart({{1, 2, 3},{30},{500, 100}})
?cart({{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}}
{}
```

## Phixmonti

`include ..\Utilitys.pmt def cart    ( ) var res    -1 get var ta -1 del    -1 get var he -1 del    ta "" != he "" != and if        he len nip for            he swap get var h drop            ta len nip for                ta swap get var t drop                ( h t ) flatten res swap 0 put var res            endfor        endfor        len if res 0 put cart endif    endifenddef /# ---------- MAIN ---------- #/ ( ( 1 2 ) ( 3 4 ) ) cartdrop res print nl nl ( ( 1776 1789 ) ( 7 12 ) ( 4 14 23 ) ( 0 1 ) ) cartdrop res print nl nl ( ( 1 2 3 ) ( 30 ) ( 500 100 ) ) cartdrop res print nl nl ( ( 1 2 ) ( ) ) cartdrop res print nl nl`

## PicoLisp

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

## Prolog

` product([A|_], Bs, [A, B]) :- member(B, Bs).product([_|As], Bs, X) :- product(As, Bs, X). `
Output:
```?- findall(X, product([1,2],[3,4],X), S).
S = [[1, 3], [1, 4], [2, 3], [2, 4]].

?- findall(X, product([3,4],[1,2],X), S).
S = [[3, 1], [3, 2], [4, 1], [4, 2]].

?- findall(X, product([1,2,3],[],X), S).
S = [].

?- findall(X, product([],[1,2,3],X), S).
S = [].
```

## Python

### Using itertools

`import itertools def cp(lsts):    return list(itertools.product(*lsts)) if __name__ == '__main__':    from pprint import pprint as pp     for lists in [[[1,2],[3,4]], [[3,4],[1,2]], [[], [1, 2]], [[1, 2], []],                  ((1776, 1789),  (7, 12), (4, 14, 23), (0, 1)),                  ((1, 2, 3), (30,), (500, 100)),                  ((1, 2, 3), (), (500, 100))]:        print(lists, '=>')        pp(cp(lists), indent=2) `
Output:
```[[1, 2], [3, 4]] =>
[(1, 3), (1, 4), (2, 3), (2, 4)]
[[3, 4], [1, 2]] =>
[(3, 1), (3, 2), (4, 1), (4, 2)]
[[], [1, 2]] =>
[]
[[1, 2], []] =>
[]
((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)]
((1, 2, 3), (30,), (500, 100)) =>
[ (1, 30, 500),
(1, 30, 100),
(2, 30, 500),
(2, 30, 100),
(3, 30, 500),
(3, 30, 100)]
((1, 2, 3), (), (500, 100)) =>
[]```

### Using the 'Applicative' abstraction

This task calls for alternative approaches to defining cartesian products, and one particularly compact alternative route to a native cartesian product (in a more mathematically reasoned idiom of programming) is through the Applicative abstraction (see Applicative Functor), which is slightly more general than the possibly better known monad structure. Applicative functions are provided off-the-shelf by languages like Agda, Idris, Haskell and Scala, and can usefully be implemented in any language, including Python, which supports higher-order functions.

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

`# ap (<*>) :: [(a -> b)] -> [a] -> [b]def ap(fs):    return lambda xs: foldl(        lambda a: lambda f: a + foldl(            lambda a: lambda x: a + [f(x)])([])(xs)    )([])(fs)`

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

`ap(map(Tuple, xs))`

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.

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:

`# nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]def nAryCartProd(xxs):    return foldl1(cartesianProduct)(        xxs    )`

For example:

`# Two lists -> list of tuples  # cartesianProduct :: [a] -> [b] -> [(a, b)]def cartesianProduct(xs):    return ap(map(Tuple, xs))  # List of lists -> list of tuples # nAryCartProd :: [[a], [b], [c] ...] -> [(a, b, c ...)]def nAryCartProd(xxs):    return foldl1(cartesianProduct)(        xxs    )  # main :: IO ()def main():    # Product of lists of different types    print (        'Product of two lists of different types:'    )    print(        cartesianProduct(['a', 'b', 'c'])(            [1, 2]        )    )     # TESTS OF PRODUCTS OF TWO LISTS     print(        '\nSpecified tests of products of two lists:'    )    print(        cartesianProduct([1, 2])([3, 4]),        ' <--> ',        cartesianProduct([3, 4])([1, 2])    )    print (        cartesianProduct([1, 2])([]),        ' <--> ',        cartesianProduct([])([1, 2])    )     # TESTS OF N-ARY CARTESIAN PRODUCTS     print('\nSpecified tests of nAry products:')    for xs in nAryCartProd([[1776, 1789], [7, 12], [4, 14, 23], [0, 1]]):        print(xs)     for xs in (        map_(nAryCartProd)(            [                [[1, 2, 3], [30], [500, 100]],                [[1, 2, 3], [], [500, 100]]            ]        )    ):        print(            xs        ) # GENERIC -------------------------------------------------  # Applicative function for lists # ap (<*>) :: [(a -> b)] -> [a] -> [b]def ap(fs):    return lambda xs: foldl(        lambda a: lambda f: a + foldl(            lambda a: lambda x: a + [f(x)])([])(xs)    )([])(fs)  # foldl :: (a -> b -> a) -> a -> [b] -> adef foldl(f):    def go(v, xs):        a = v        for x in xs:            a = f(a)(x)        return a    return lambda acc: lambda xs: go(acc, xs)  # foldl1 :: (a -> a -> a) -> [a] -> adef foldl1(f):    return lambda xs: foldl(f)(xs[0])(        xs[1:]    ) if xs else None  # map :: (a -> b) -> [a] -> [b]def map_(f):    return lambda xs: list(map(f, xs))  # Tuple :: a -> b -> (a, b)def Tuple(x):    return lambda y: (        x + (y,)    ) if tuple is type(x) else (x, y)  # TEST ----------------------------------------------------if __name__ == '__main__':    main()`
Output:
```Product of two lists of different types:
[('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2)]

Specified tests of products of two lists:
[(1, 3), (1, 4), (2, 3), (2, 4)]  <-->  [(3, 1), (3, 2), (4, 1), (4, 2)]
[]  <-->  []

Specified tests of nAry products:
(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)]
[]```

## Quackery

`  [ [] unrot    swap witheach      [ over witheach          [ over nested             swap nested join             nested dip rot join             unrot ]      drop ] drop ]             is cartprod ( [ [ --> [ )   ' [ 1 2 ] ' [ 3 4 ] cartprod echo cr  ' [ 3 4 ] ' [ 1 2 ] cartprod echo cr  ' [ 1 2 ] ' [     ] cartprod echo cr  ' [     ] ' [ 1 2 ] cartprod echo cr`
Output:
```[ [ 1 3 ] [ 1 4 ] [ 2 3 ] [ 2 4 ] ]
[ [ 3 1 ] [ 3 2 ] [ 4 1 ] [ 4 2 ] ]
[ ]
[ ]
```

## R

` one_w_many <- function(one, many) lapply(many, function(x) c(one,x)) # Let's define an infix operator to perform a cartesian product. "%p%" <- function( a, b ) {  p = c( sapply(a, function (x) one_w_many(x, b) ) )  if (is.null(unlist(p))) list() else p} display_prod <-  function (xs) { for (x in xs) cat( paste(x, collapse=", "), "\n" ) } fmt_vec <- function(v) sprintf("(%s)", paste(v, collapse=', ')) go <- function (...) {  cat("\n", paste( sapply(list(...),fmt_vec), collapse=" * "), "\n")  prod = Reduce( '%p%', list(...) )  display_prod( prod ) } `

Simple tests:

` > display_prod(  c(1, 2) %p% c(3, 4)  )1, 31, 42, 32, 4> display_prod(  c(3, 4) %p% c(1, 2)  )3, 13, 24, 14, 2> display_prod(  c(3, 4) %p% c()  )> `

Tougher tests:

` 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(), c(500, 100) ) `
Output:
``` (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

(1, 2, 3) * (30) * (500, 100)
1, 30, 500
1, 30, 100
2, 30, 500
2, 30, 100
3, 30, 500
3, 30, 100

(1, 2, 3) * () * (500, 100)
```

## Racket

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

## Raku

(formerly Perl 6)

Works with: Rakudo version 2017.06

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

`# cartesian product of two lists using the X cross meta-operatorsay (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] reduce cross meta-operatorsay [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))
()```

## REXX

### version 1

This REXX version isn't limited by the number of lists or the number of sets within a list.

`/*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     a=1   for words(x.i)               /*obtain the elements of the first list*/         do   j=i+1 for #-1                      /*   "    "  subsequent lists.         */           do b=1   for words(x.j)               /*   "    " elements of subsequent list*/           \$=\$',('word(x.i, a)","word(x.j, b)')' /*append partial Cartesian product ──►\$*/           end   /*b*/         end     /*j*/       end       /*a*/     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)}
```

### version 2

`/* REXX computes the Cartesian Product of up to 4 sets */Call cart '{1, 2} x {3, 4}'Call cart '{3, 4} x {1, 2}'Call cart '{1, 2} x {}'Call cart '{} x {1, 2}'Call cart '{1776, 1789} x {7, 12} x {4, 14, 23} x {0, 1}'Call cart '{1, 2, 3} x {30} x {500, 100}'Call cart '{1, 2, 3} x {} x {500, 100}'Exit cart:  Parse Arg sl  Say sl  Do i=1 By 1 while pos('{',sl)>0    Parse Var sl '{' list '}' sl    Do j=1 By 1 While list<>''      Parse Var list e.i.j . ',' list      End    n.i=j-1    If n.i=0 Then Do /* an empty set */      Say '{}'      Say ''      Return      End    End  n=i-1  ct2.=0  Do i=1 To n.1    Do j=1 To n.2      z=ct2.0+1      ct2.z=e.1.i e.2.j      ct2.0=z      End    End  If n<3 Then    Return output(2)  ct3.=0  Do i=1 To ct2.0    Do k=1 To n.3      z=ct3.0+1      ct3.z=ct2.i e.3.k      ct3.0=z      End    End  If n<4 Then    Return output(3)  ct4.=0  Do i=1 To ct3.0    Do l=1 To n.4      z=ct4.0+1      ct4.z=ct3.i e.4.l      ct4.0=z      End    End  Return output(4) output:  Parse Arg u  Do v=1 To value('ct'u'.0')    res='{'translate(value('ct'u'.'v),',',' ')'}'    Say res    End  Say ' '  Return 0`
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}
{}

{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}
{}```

## Ring

` # Project : Cartesian product of two or more lists list1 = [[1,2],[3,4]]list2 = [[3,4],[1,2]]cartesian(list1)cartesian(list2) func cartesian(list1)     for n = 1 to len(list1[1])         for m = 1 to len(list1[2])             see "(" + list1[1][n] + ", " + list1[2][m] + ")" + nl         next      next      see nl `

Output:

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

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

## Ruby

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

```

## Rust

`fn cartesian_product(lists: &Vec<Vec<u32>>) -> Vec<Vec<u32>> {    let mut res = vec![];     let mut list_iter = lists.iter();    if let Some(first_list) = list_iter.next() {        for &i in first_list {            res.push(vec![i]);        }    }    for l in list_iter {        let mut tmp = vec![];        for r in res {            for &el in l {                let mut tmp_el = r.clone();                tmp_el.push(el);                tmp.push(tmp_el);            }        }        res = tmp;    }    res} fn main() {    let cases = vec![        vec![vec![1, 2], vec![3, 4]],        vec![vec![3, 4], vec![1, 2]],        vec![vec![1, 2], vec![]],        vec![vec![], vec![1, 2]],        vec![vec![1776, 1789], vec![7, 12], vec![4, 14, 23], vec![0, 1]],        vec![vec![1, 2, 3], vec![30], vec![500, 100]],        vec![vec![1, 2, 3], vec![], vec![500, 100]],    ];    for case in cases {        println!(            "{}\n{:?}\n",            case.iter().map(|c| format!("{:?}", c)).collect::<Vec<_>>().join(" × "),            cartesian_product(&case)        )    }} `
Output:
```[1, 2] × [3, 4]
[[1, 3], [1, 4], [2, 3], [2, 4]]
[3, 4] × [1, 2]
[[3, 1], [3, 2], [4, 1], [4, 2]]
[1, 2] × []
[]
[] × [1, 2]
[]
[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]]
[1, 2, 3] × [30] × [500, 100]
[[1, 30, 500], [1, 30, 100], [2, 30, 500], [2, 30, 100], [3, 30, 500], [3, 30, 100]]
[1, 2, 3] × [] × [500, 100]
[]

```

## Scala

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:
`{}`

## Scheme

` (define cartesian-product (lambda (xs ys) (if (or (zero? (length xs)) (zero? (length ys)))     '()     (fold append (map (lambda (x) (map (lambda (y) (list x y)) ys)) xs))))) (define nary-cartesian-product (lambda (ls) (if (fold (lambda (a b) (or a b)) (map (compose zero? length) ls))     '()     (map flatten (fold cartesian-product ls))))) > (cartesian-product '(1 2) '(3 4))((1 3) (1 4) (2 3) (2 4))> (cartesian-product '(3 4) '(1 2))((3 1) (3 2) (4 1) (4 2))> (cartesian-product '(1 2) '())()> (cartesian-product '() '(1 2))()> (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)) `

## Sidef

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

`cartesian([[1,2], [3,4], [5,6]]).saycartesian([[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}`

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

## SQL

If we create lists as tables with one column, cartesian product is easy.

`-- set up list 1CREATE TABLE L1 (VALUE INTEGER);INSERT INTO L1 VALUES (1);INSERT INTO L1 VALUES (2);-- set up list 2CREATE TABLE L2 (VALUE INTEGER);INSERT INTO L2 VALUES (3);INSERT INTO L2 VALUES (4);-- get the productSELECT * FROM L1, L2;`
Output:
```     VALUE      VALUE
---------- ----------
1          3
1          4
2          3
2          4```
You should be able to be more explicit should get the same result:
`SELECT * FROM L1 CROSS JOIN L2;`

Product with an empty list works as expected (using the tables created above):

`DELETE FROM L2;SELECT * FROM L1, L2;`
Output:
`no rows selected`
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):
`INSERT INTO L1 VALUES (3);INSERT INTO L2 VALUES (30);CREATE TABLE L3 (VALUE INTEGER);INSERT INTO L3 VALUES (500);INSERT INTO L3 VALUES (100);-- product works the same for as many "lists" as you'd likeSELECT * FROM L1, L2, L3;`
Output:
```     VALUE      VALUE      VALUE
---------- ---------- ----------
1         30        500
2         30        500
3         30        500
1         30        100
2         30        100
3         30        100```

## Standard ML

`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

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 |     +---------------------+`

## Swift

Translation of: Scala
`func + <T>(el: T, arr: [T]) -> [T] {  var ret = arr   ret.insert(el, at: 0)   return ret} func cartesianProduct<T>(_ arrays: [T]...) -> [[T]] {  guard let head = arrays.first else {    return []  }   let first = Array(head)   func pel(    _ el: T,    _ ll: [[T]],    _ a: [[T]] = []  ) -> [[T]] {    switch ll.count {    case 0:      return a.reversed()    case _:      let tail = Array(ll.dropFirst())      let head = ll.first!       return pel(el, tail, el + head + a)    }  }   return arrays.reversed()    .reduce([first], {res, el in el.flatMap({ pel(\$0, res) }) })    .map({ \$0.dropLast(first.count) })}  print(cartesianProduct([1, 2], [3, 4]))print(cartesianProduct([3, 4], [1, 2]))print(cartesianProduct([1, 2], []))print(cartesianProduct([1776, 1789], [7, 12], [4, 14, 23], [0, 1]))print(cartesianProduct([1, 2, 3], [30], [500, 100]))print(cartesianProduct([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]]
[]```

## Tailspin

` '{1,2}x{3,4} = \$:[by [1,2]..., by [3,4]...];' -> !OUT::write '{3,4}x{1,2} = \$:[by [3,4]..., by [1,2]...];' -> !OUT::write '{1,2}x{} = \$:[by [1,2]..., by []...];' -> !OUT::write '{}x{1,2} = \$:[by []..., by [1,2]...];' -> !OUT::write '{1776, 1789} × {7, 12} × {4, 14, 23} × {0, 1} = \$:[by [1776, 1789]..., by [7, 12]..., by [4, 14, 23]..., by [0, 1]...];' -> !OUT::write '{1, 2, 3} × {30} × {500, 100} = \$:[by [1, 2, 3] ..., by [30]..., by [500, 100]...];' -> !OUT::write '{1, 2, 3} × {} × {500, 100} = \$:[by [1, 2, 3]..., by []..., by [500, 100]...];' -> !OUT::write // You can also generate structures with named fields'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 `
Output:
```{1,2}x{3,4} = [1, 3][2, 3][1, 4][2, 4]
{3,4}x{1,2} = [3, 1][4, 1][3, 2][4, 2]
{1,2}x{} =
{}x{1,2} =
{1776, 1789} × {7, 12} × {4, 14, 23} × {0, 1} = [1776, 7, 4, 0][1789, 7, 4, 0][1776, 12, 4, 0][1789, 12, 4, 0][1776, 7, 14, 0][1789, 7, 14, 0][1776, 12, 14, 0][1789, 12, 14, 0][1776, 7, 23, 0][1789, 7, 23, 0][1776, 12, 23, 0][1789, 12, 23, 0][1776, 7, 4, 1][1789, 7, 4, 1][1776, 12, 4, 1][1789, 12, 4, 1][1776, 7, 14, 1][1789, 7, 14, 1][1776, 12, 14, 1][1789, 12, 14, 1][1776, 7, 23, 1][1789, 7, 23, 1][1776, 12, 23, 1][1789, 12, 23, 1]
{1, 2, 3} × {30} × {500, 100} = [1, 30, 500][2, 30, 500][3, 30, 500][1, 30, 100][2, 30, 100][3, 30, 100]
{1, 2, 3} × {} × {500, 100} =
year {1776, 1789} × month {7, 12} × day {4, 14, 23} = {day=4, month=7, year=1776}{day=4, month=7, year=1789}{day=4, month=12, year=1776}{day=4, month=12, year=1789}{day=14, month=7, year=1776}{day=14, month=7, year=1789}{day=14, month=12, year=1776}{day=14, month=12, year=1789}{day=23, month=7, year=1776}{day=23, month=7, year=1789}{day=23, month=12, year=1776}{day=23, month=12, year=1789}
```

## Tcl

` proc cartesianProduct {l1 l2} {  set result {}  foreach el1 \$l1 {    foreach el2 \$l2 {      lappend result [list \$el1 \$el2]    }  }  return \$result} puts "simple"puts "result: [cartesianProduct {1 2} {3 4}]"puts "result: [cartesianProduct {3 4} {1 2}]"puts "result: [cartesianProduct {1 2} {}]"puts "result: [cartesianProduct {} {3 4}]" proc cartesianNaryProduct {lists} {  set result {{}}  foreach l \$lists {    set res {}    foreach comb \$result {      foreach el \$l {        lappend res [linsert \$comb end \$el]      }    }    set result \$res  }  return \$result} puts "n-ary"puts "result: [cartesianNaryProduct {{1776 1789} {7 12} {4 14 23} {0 1}}]"puts "result: [cartesianNaryProduct {{1 2 3} {30} {500 100}}]"puts "result: [cartesianNaryProduct {{1 2 3} {} {500 100}}]"  `
Output:
```simple
result: {1 3} {1 4} {2 3} {2 4}
result: {3 1} {3 2} {4 1} {4 2}
result:
result:
n-ary
result: {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}
result: {1 30 500} {1 30 100} {2 30 500} {2 30 100} {3 30 500} {3 30 100}
result:
```

## UNIX Shell

The UNIX shells don't allow passing or returning arrays from functions (other than pass-by-name shenanigans), but as pointed out in the Perl entry, wildcard brace expansion (in bash, ksh, zsh) does a Cartesian product if there's more than one set of alternatives. It doesn't handle the empty-list case (an empty brace expansion item is treated as a single item that is equal to the empty string), but otherwise it works:

```   \$ printf '%s' "("{1,2},{3,4}")"; printf '\n'
(1,3)(1,4)(2,3)(2,4)
\$ printf '%s' "("{3,4},{1,2}")"; printf '\n'
(3,1)(3,2)(4,1)(4,2)
```

More than two lists is not a problem:

```   \$ printf '%s\n' "("{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)
\$ printf '%s\n' "("{1,2,3},30,{500,100}")"
(1,30,500)
(1,30,100)
(2,30,500)
(2,30,100)
(3,30,500)
(3,30,100)
```

## Visual Basic .NET

Translation of: C#
`Imports System.Runtime.CompilerServices Module Module1     <Extension()>    Function CartesianProduct(Of T)(sequences As IEnumerable(Of IEnumerable(Of T))) As IEnumerable(Of IEnumerable(Of T))        Dim emptyProduct As IEnumerable(Of IEnumerable(Of T)) = {Enumerable.Empty(Of T)}        Return sequences.Aggregate(emptyProduct, Function(accumulator, sequence) From acc In accumulator From item In sequence Select acc.Concat({item}))    End Function     Sub Main()        Dim empty(-1) As Integer        Dim list1 = {1, 2}        Dim list2 = {3, 4}        Dim list3 = {1776, 1789}        Dim list4 = {7, 12}        Dim list5 = {4, 14, 23}        Dim list6 = {0, 1}        Dim list7 = {1, 2, 3}        Dim list8 = {30}        Dim list9 = {500, 100}         For Each sequnceList As Integer()() In {            ({list1, list2}),            ({list2, list1}),            ({list1, empty}),            ({empty, list1}),            ({list3, list4, list5, list6}),            ({list7, list8, list9}),            ({list7, empty, list9})        }            Dim cart = sequnceList.CartesianProduct().Select(Function(tuple) \$"({String.Join(", ", tuple)})")            Console.WriteLine(\$"{{{String.Join(", ", cart)}}}")        Next    End Sub End Module`
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)}
{}```

## Wren

Translation of: Kotlin
Library: Wren-seq
`import "/seq" for Lst var prod2 = Fn.new { |l1, l2|    var res = []    for (e1 in l1) {        for (e2 in l2) res.add([e1, e2])    }    return res} var prodN = Fn.new { |ll|    if (ll.count < 2) Fiber.abort("There must be at least two lists.")    var p2 = prod2.call(ll[0], ll[1])    return ll.skip(2).reduce(p2) { |acc, l| prod2.call(acc, l) }.map { |l| Lst.flatten(l) }.toList} var printProdN = Fn.new { |ll|    System.print("%(ll.join(" x ")) = ")    System.write("[\n    ")    System.print(prodN.call(ll).join("\n    "))    System.print("]\n")} System.print("[1, 2] x [3, 4] = %(prodN.call([ [1, 2], [3, 4] ]))")System.print("[3, 4] x [1, 2] = %(prodN.call([ [3, 4], [1, 2] ]))")System.print("[1, 2] x []     = %(prodN.call([ [1, 2], [] ]))")System.print("[]     x [1, 2] = %(prodN.call([ [], [1, 2] ]))")System.print("[1, a] x [2, b] = %(prodN.call([ [1, "a"], [2, "b"] ]))")System.print()printProdN.call([ [1776, 1789], [7, 12], [4, 14, 23], [0, 1] ])printProdN.call([ [1, 2, 3], [30], [500, 100] ])printProdN.call([ [1, 2, 3], [], [500, 100] ])printProdN.call([ [1, 2, 3], [30], ["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]
]
```

## zkl

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