Cartesian product of two or more lists: Difference between revisions
m
→{{header|langur}}
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
Langurmonkey (talk | contribs) |
||
| (22 intermediate revisions by 10 users not shown) | |||
Line 281:
{(1,30,500),(1,30,100),(2,30,500),(2,30,100),(3,30,500),(3,30,100)}
{}</pre>
=={{header|ALGOL 68}}==
Using a 1-dimensional array of INT to represent a list and a 2-dimensional array ( [,]INT ) to represent a product of two (or more) lists.
<br>
A list of lists is represented by a 1-dimensional array of 1-dimensional arrays of INT ([][]INT).
<syntaxhighlight lang="algol68">
BEGIN # Cartesian Product #
# Cartesian product operators #
PRIO X = 7; # give X he same priority as * #
# returns the Cartesian product of the lists a and b #
OP X = ( []INT a, b )[,]INT:
BEGIN
[]INT a1 = a[ AT 1 ];
[]INT b1 = b[ AT 1 ];
INT len = UPB a1 * UPB b1;
[ 1 : len, 1 : IF len > 0 THEN 2 ELSE 0 FI ]INT result;
INT pos := 0;
FOR i TO UPB a1 DO
FOR j TO UPB b1 DO
pos +:= 1;
result[ pos, 1 ] := a1[ i ];
result[ pos, 2 ] := b1[ j ]
OD
OD;
result
END # X # ;
# returns the Cartesian product of the Cartesian product a and list b #
OP X = ( [,]INT a, []INT b )[,]INT:
BEGIN
[,]INT a1 = a[ AT 1, AT 1 ];
[]INT b1 = b[ AT 1 ];
INT len = 1 UPB a1 * UPB b1;
INT width = IF len <= 0 THEN 0 ELSE 2 UPB a1 + 1 FI;
[ 1 : len, 1 : width ]INT result;
INT pos := 0;
FOR i TO 1 UPB a1 DO
FOR j TO UPB b1 DO
result[ pos +:= 1, 1 : width - 1 ] := a1[ i, : ];
result[ pos, width ] := b1[ j ]
OD
OD;
result
END # X # ;
# returns the Cartesian product of the lists in a #
OP X = ( [][]INT a )[,]INT:
IF UPB a <= LWB a
THEN # zero or 1 list #
[,]INT()
ELSE # 2 or more lists #
FLEX[ 1 : 0, 1 : 0 ]INT result := a[ LWB a ] X a[ LWB a + 1 ];
FOR i FROM LWB a + 2 TO UPB a DO
result := result X a[ i ]
OD;
result
FI # X # ;
# print a Cartesian product #
PROC print product = ( [,]INT p )VOID:
BEGIN
print( ( "[" ) );
STRING close := "]";
STRING open := "(";
FOR i FROM 1 LWB p TO 1 UPB p DO
STRING separator := open;
FOR j FROM 2 LWB p TO 2 UPB p DO
print( ( separator, whole( p[ i, j ], 0 ) ) );
separator := ","
OD;
open := "),(";
close := ")]"
OD;
print( ( close ) )
END # print product # ;
# print a list #
PROC print list = ( []INT t )VOID:
BEGIN
print( ( "[" ) );
STRING separator := "";
FOR i FROM LWB t TO UPB t DO
print( ( separator, whole( t[ i ], 0 ) ) );
separator := ","
OD;
print( ( "]" ) )
END # print list # ;
BEGIN # test the X operators #
# prints the product of two lists #
PROC print lxl = ( []INT a, b )VOID:
BEGIN
print list( a );print( ( "X" ) );print list( b );
print( ( "=" ) );print product( a X b );
print( ( newline ) )
END # print lxl # ;
# prints the product of a list of lists #
PROC print xll = ( [][]INT a )VOID:
IF LWB a < UPB a THEN
# non empty list of lists #
print list( a[ LWB a ] );
FOR i FROM LWB a + 1 TO UPB a DO
print( ( "X" ) );print list( a[ i ] )
OD;
print( ( "=" ) );print product( X a );
print( ( newline ) )
FI # print xll # ;
print lxl( ( 1, 2 ), ( 3, 4 ) );
print lxl( ( 3, 4 ), ( 1, 2 ) );
print lxl( ( 1, 2 ), () );
print lxl( (), ( 1, 2 ) );
print xll( ( ( 1776, 1789 ), ( 7, 12 ), ( 4, 14, 23 ), ( 0, 1 ) ) );
print xll( ( ( 1, 2, 3 ), ( 30 ), ( 500, 100 ) ) );
print xll( ( ( 1, 2, 3 ), (), ( 500, 100 ) ) )
END
END
</syntaxhighlight>
{{out}}
<pre>
[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]=[]
</pre>
=={{header|APL}}==
Line 347 ⟶ 469:
↑nary_cart(1 2 3)(⍬)(50 100) ⍝ empty output
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">-- CARTESIAN PRODUCTS ---------------------------------------------------------
Line 696 ⟶ 819:
(.3 30 100)
.</pre>
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
<syntaxhighlight lang="qbasic">100 HOME : rem 10 CLS FOR Chipmunk Basic & GW-BASIC
110 DIM array(2,2)
120 array(1,1) = 1 : array(1,2) = 2
130 array(2,1) = 3 : array(2,2) = 4
140 GOSUB 190
150 array(1,1) = 3 : array(1,2) = 4
160 array(2,1) = 1 : array(2,2) = 2
170 GOSUB 190
180 END
190 rem SUB cartesian(list)
200 u1 = 2 : u2 = 2
210 FOR i = 1 TO u1
220 PRINT "{ ";
230 FOR j = 1 TO u2
240 PRINT array(i,j);
250 IF j < u1 THEN PRINT ", ";
260 NEXT j
270 PRINT "}";
280 IF i < u2 THEN PRINT " x ";
290 NEXT i
300 PRINT " = { ";
310 FOR i = 1 TO u1
320 FOR j = 1 TO u2
330 PRINT "{ "; array(1,i); ", "; array(2,j); "} ";
340 IF i < u2 THEN PRINT ", ";
350 IF i => u2 THEN IF j < u1 THEN PRINT ", ";
360 NEXT j
370 NEXT i
380 PRINT "}"
390 RETURN</syntaxhighlight>
==={{header|BASIC256}}===
<syntaxhighlight lang="vb">arraybase 1
subroutine cartesian(list)
u1 = list[?][]
u2 = list[][?]
for i = 1 to u1
print "{";
for j = 1 to u2
print list[i,j];
if j < u1 then print ", ";
next
print "}";
if i < u2 then print " x ";
next i
print " = { ";
for i = 1 to u1
for j = 1 to u2
print "{"; list[1, i]; ", "; list[2, j]; "} ";
if i < u2 then
print ", ";
else
if j < u1 then print ", ";
end if
next j
next i
print "}"
end subroutine
dim list1 = {{1,2},{3,4}}
dim list2 = {{3,4},{1,2}}
call cartesian(list1)
call cartesian(list2)
end</syntaxhighlight>
{{out}}
<pre>{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} }</pre>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 cls
110 dim array(2,2)
120 array(1,1) = 1 : array(1,2) = 2
130 array(2,1) = 3 : array(2,2) = 4
140 gosub 190
150 array(1,1) = 3 : array(1,2) = 4
160 array(2,1) = 1 : array(2,2) = 2
170 gosub 190
180 end
190 rem sub cartesian(list)
200 u1 = 2 : u2 = 2
210 for i = 1 to u1
220 print "{ ";
230 for j = 1 to u2
240 print array(i,j);
250 if j < u1 then print ", ";
260 next j
270 print "}";
280 if i < u2 then print " x ";
290 next i
300 print " = { ";
310 for i = 1 to u1
320 for j = 1 to u2
330 print "{ ";array(1,i);", ";array(2,j);"} ";
340 if i < u2 then
350 print ", ";
360 else
370 if j < u1 then print ", ";
380 endif
390 next j
400 next i
410 print "}"
420 return</syntaxhighlight>
==={{header|Gambas}}===
<syntaxhighlight lang="vbnet">Public array[2, 2] As Integer
Public Sub Main()
array[0, 0] = 1
array[0, 1] = 2
array[1, 0] = 3
array[1, 1] = 4
cartesian(array)
array[0, 0] = 3
array[0, 1] = 4
array[1, 0] = 1
array[1, 1] = 2
cartesian(array)
End
Sub cartesian(arr As Integer[])
Dim u1 As Integer = arr.Max - 2
Dim u2 As Integer = arr.Max - 2
Dim i As Integer, j As Integer
For i = 0 To u1
Print "{";
For j = 0 To u2
Print arr[i, j];
If j < u1 Then Print ",";
Next
Print "}";
If i < u2 Then Print " x ";
Next
Print " = {";
For i = 0 To u1
For j = 0 To u2
Print "{"; arr[0, i]; ","; arr[1, j]; "}";
If i < u2 Then
Print ", ";
Else
If j < u1 Then Print ", ";
End If
Next
Next
Print "}"
End Sub</syntaxhighlight>
==={{header|GW-BASIC}}===
{{works with|Chipmunk Basic}}
{{works with|PC-BASIC|any}}
{{works with|QBasic}}
{{works with|MSX-BASIC}}
<syntaxhighlight lang="qbasic">100 CLS
110 DIM ARR(2,2)
120 ARR(1,1) = (1) : ARR(1,2) = (2)
130 ARR(2,1) = (3) : ARR(2,2) = (4)
140 GOSUB 190
150 ARR(1,1) = 3 : ARR(1,2) = 4
160 ARR(2,1) = 1 : ARR(2,2) = 2
170 GOSUB 190
180 END
190 REM SUB cartesian(list)
200 U1 = 2 : U2 = 2
210 FOR I = 1 TO U1
220 PRINT "{";
230 FOR J = 1 TO U2
240 PRINT ARR(I,J);
250 IF J < U1 THEN PRINT ",";
260 NEXT J
270 PRINT "}";
280 IF I < U2 THEN PRINT " x ";
290 NEXT I
300 PRINT " = {";
310 FOR I = 1 TO U1
320 FOR J = 1 TO U2
330 PRINT "{"; ARR(1,I); ","; ARR(2,J); "}";
340 IF I < U2 THEN PRINT ", ";
350 IF I => U2 THEN IF J < U1 THEN PRINT ",";
360 NEXT J
370 NEXT I
380 PRINT "}"
390 RETURN</syntaxhighlight>
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">DECLARE SUB cartesian (arr!())
CLS
DIM array(2, 2)
array(1, 1) = 1: array(1, 2) = 2
array(2, 1) = 3: array(2, 2) = 4
CALL cartesian(array())
array(1, 1) = 3: array(1, 2) = 4
array(2, 1) = 1: array(2, 2) = 2
CALL cartesian(array())
END
SUB cartesian (arr())
u1 = 2: u2 = 2
FOR i = 1 TO u1
PRINT "{";
FOR j = 1 TO u2
PRINT arr(i, j);
IF j < u1 THEN PRINT ",";
NEXT j
PRINT "}";
IF i < u2 THEN PRINT " x ";
NEXT i
PRINT " = {";
FOR i = 1 TO u1
FOR j = 1 TO u2
PRINT "{"; arr(1, i); ","; arr(2, j); "}";
IF i < u2 THEN
PRINT ", ";
ELSE
IF j < u1 THEN PRINT ", ";
END IF
NEXT j
NEXT i
PRINT "}"
END SUB</syntaxhighlight>
==={{header|Run BASIC}}===
{{works with|Just BASIC}}
{{works with|Liberty BASIC}}
<syntaxhighlight lang="vb">cls
dim array(2,2)
array(1,1) = 1 : array(1,2) = 2
array(2,1) = 3 : array(2,2) = 4
gosub [cartesian]
array(1,1) = 3 : array(1,2) = 4
array(2,1) = 1 : array(2,2) = 2
gosub [cartesian]
end
[cartesian]
u1 = 2 : u2 = 2
for i = 1 to u1
print "{";
for j = 1 to u2
print array(i,j);
if j < u1 then print ",";
next j
print "}";
if i < u2 then print " x ";
next i
print " = {";
for i = 1 to u1
for j = 1 to u2
print "{"; array(1,i); ","; array(2,j); "}";
if i < u2 then
print ",";
else
if j < u1 then print ",";
end if
next j
next i
print "}"
return</syntaxhighlight>
=={{header|C}}==
Recursive implementation for computing the Cartesian product of lists. In the pursuit of making it as interactive as possible, the parsing function ended up taking the most space. The product set expression must be supplied enclosed by double quotes. Prints out usage on incorrect invocation.
Line 1,348 ⟶ 1,747:
[]</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
proc cart2 a[] b[] . p[][] .
p[][] = [ ]
for a in a[]
for b in b[]
p[][] &= [ a b ]
.
.
.
cart2 [ 1 2 ] [ 3 4 ] r[][]
print r[][]
cart2 [ 3 4 ] [ 1 2 ] r[][]
print r[][]
cart2 [ 1 2 ] [ ] r[][]
print r[][]
cart2 [ ] [ 1 2 ] r[][]
print r[][]
</syntaxhighlight>
=={{header|Erlang}}==
Can do this with list comprehensions.
<syntaxhighlight lang="erlang">
-module(cartesian).
-export([product/2]).
product(S1, S2) -> [{A,B} || A <- S1, B <- S2].
</syntaxhighlight>
{{Out}}
<pre>
2> cartesian:product([],[1,2,3]).
[]
3> cartesian:product([1,2,3],[]).
[]
4> cartesian:product([1,2],[3,4]).
[{1,3},{1,4},{2,3},{2,4}]
5> cartesian:product([3,4],[1,2]).
[{3,1},{3,2},{4,1},{4,2}]
</pre>
=={{header|F Sharp|F#}}==
===The Task===
Line 1,382 ⟶ 1,822:
cP [[1;2;3];[];[500;100]] -> []
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">IN: scratchpad { 1 2 } { 3 4 } cartesian-product .
Line 1,494 ⟶ 1,935:
end program cartesian_product
</syntaxhighlight>
{{out}}
{3,4} x {1,2} = {{3,1},{3,2},{4,1},{4,2}}
{1,2} x {} = {}
{} x {1,2} = {}</pre>
=={{header|FreeBASIC}}==
I'll leave the extra credit part for someone else. It's just going to amount to repeatedly finding Cartesian products and [[Flatten a list|flattening]] the result, so considerably less interesting than Cartesian products where the list items themselves can be lists.
Line 1,571 ⟶ 2,011:
{}
</pre>
=={{header|Fōrmulæ}}==
'''Solution'''
No program is needed, the cartesian product is an intrinsic operation in Fōrmulæ
'''Test case 1.''' No commutativity
[[File:Fōrmulæ - Cartesian product of two or more lists 01.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 02.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 03.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 04.png]]
'''Test case 2.''' With an empty list
[[File:Fōrmulæ - Cartesian product of two or more lists 05.png]]
[[File:Fōrmulæ - Empty list.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 06.png]]
[[File:Fōrmulæ - Empty list.png]]
'''Test case 3.''' Extra credit. n-ary cartesian product
[[File:Fōrmulæ - Cartesian product of two or more lists 07.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 08.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 09.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 10.png]]
[[File:Fōrmulæ - Cartesian product of two or more lists 11.png]]
[[File:Fōrmulæ - Empty list.png]]
=={{header|Go}}==
'''Basic Task'''
Line 2,042 ⟶ 2,517:
</syntaxhighlight>
=={{header|JavaScript}}==
function cartesian(m){
if(!m.length)return[[]];
let tails=cartesian(m.slice(1));
return(m[0].flatMap(h=>tails.map(t=>[h].concat(t))));
}
===ES6===
====Functional====
Line 2,322 ⟶ 2,803:
[]</pre>
=={{header|jq}}==
Line 2,514 ⟶ 2,996:
</pre>
=={{header|langur}}==
<syntaxhighlight lang="langur">val .X = fn(... .x) { .x }
writeln mapX(.X, [1, 2], [3, 4]) == [[1, 3], [1, 4], [2, 3], [2, 4]]
writeln mapX(.X
writeln
writeln()
writeln mapX .X, [1776, 1789], [7, 12], [4, 14, 23], [0, 1]
writeln()
writeln mapX .X, [1, 2, 3], [30], [500, 100]
writeln()
writeln mapX .X, [1, 2, 3], [], [500, 100]
writeln()</syntaxhighlight>
Line 2,544 ⟶ 3,025:
[]
</pre>
=={{header|Lua}}==
=== Functional ===
Line 2,797 ⟶ 3,279:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">cartesianProduct[args__] := Flatten[Outer[List, args], Length[{args}] - 1]</syntaxhighlight>
=={{header|Maxima}}==
Using built-in function cartesian_product
<syntaxhighlight lang="maxima">
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});
/* {} */
</syntaxhighlight>
Using built-in function cartesian_product_list
<syntaxhighlight lang="maxima">
cartesian_product_list([1,2],[3,4]);
/* [[1,3],[1,4],[2,3],[2,4]] */
cartesian_product_list([3,4],[1,2]);
/* [[3,1],[3,2],[4,1],[4,2]] */
cartesian_product_list([1,2],[]);
/* [] */
cartesian_product_list([],[1,2]);
/* [] */
</syntaxhighlight>
Using built-in function create_list
<syntaxhighlight lang="maxima">
create_list([i,j],i,[1,2],j,[3,4]);
/* [[1,3],[1,4],[2,3],[2,4]] */
create_list([i,j],i,[3,4],j,[1,2]);
/* [[3,1],[3,2],[4,1],[4,2]] */
create_list([i,j],i,[1,2],j,[]);
/* [] */
create_list([i,j],i,[],j,[1,2]);
/* [] */
</syntaxhighlight>
Extra credit
<syntaxhighlight lang="maxima">
my_cartesian(lst1,lst2):=create_list([i,j],i,lst1,j,lst2);
n_ary_cartesian(singleargument):=block(lreduce(my_cartesian,singleargument),map(flatten,%%));
[[1776,1789],[7,12],[4,14,23],[0,1]]$
n_ary_cartesian(%);
/* [[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]]$
n_ary_cartesian(%);
/* [[1,30,500],[1,30,100],[2,30,500],[2,30,100],[3,30,500],[3,30,100]] */
[[1,2,3],[],[500,100]]$
n_ary_cartesian(%);
/* [] */
</syntaxhighlight>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE CartesianProduct;
Line 3,934 ⟶ 4,469:
(4, 2)
</pre>
=={{header|RPL}}==
≪ → a b
≪ { }
'''IF''' a SIZE b SIZE AND '''THEN'''
1 a SIZE '''FOR''' j
1 b SIZE '''FOR''' k
a j GET b k GET 2 →LIST 1 →LIST +
'''NEXT'''
'''NEXT'''
'''END'''
≫ ≫ '<span style="color:blue">CROIX</span>' STO
{1 2} {3 4} <span style="color:blue">CROIX</span>
{3 4} {1 2} <span style="color:blue">CROIX</span>
{1 2} {} <span style="color:blue">CROIX</span>
{} {1 2} <span style="color:blue">CROIX</span>
{{out}}
<pre>
4: {(1 3) (1 4) (2 3) (2 4)}
3: {(3 1) (3 2) (4 1) (4 2)}
2: {}
1: {}
</pre>
=={{header|Ruby}}==
"product" is a method of arrays. It takes one or more arrays as argument and results in the Cartesian product:
Line 3,952 ⟶ 4,510:
[]
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn cartesian_product(lists: &Vec<Vec<u32>>) -> Vec<Vec<u32>> {
Line 4,617 ⟶ 5,176:
{{trans|Kotlin}}
{{libheader|Wren-seq}}
<syntaxhighlight lang="
var prod2 = Fn.new { |l1, l2|
Line 4,712 ⟶ 5,271:
]
</pre>
=={{header|zkl}}==
Cartesian product is build into iterators or can be done with nested
| |||