Cartesian product of two lists

Question

Task

Given two lists of characters, output their Cartesian product, i.e. the list of pairings of each letter from the first list with each letter from the second list.

Example

"123456" and "abcd" give:

[["1","a"],["1","b"],["1","c"],["1","d"],["2","a"],["2","b"],["2","c"],["2","d"],["3","a"],["3","b"],["3","c"],["3","d"],["4","a"],["4","b"],["4","c"],["4","d"],["5","a"],["5","b"],["5","c"],["5","d"],["6","a"],["6","b"],["6","c"],["6","d"]]

Input

Two lists of characters or strings. The characters used will be alphanumeric a-z, A-Z, 0-9 and a character can occur both multiple times and in both inputs at the same time.

Output

The Cartesian product of the input lists. That is, a list of each possible ordered pair of a character from the first list and a character from the second list. Each pair is a list or string or similar of two characters, or of two length-one strings. The output's length will be equal to the product of the lengths of the inputs.

The pairs must be listed in order; first listing the first character of the first list with the first of the second list, followed by all the pairings of the first character of the first list. The last pair consists of the last character of the first list together with the last character of the second list.

The output must be a flat list of pairs; not a 2D matrix where pairs are grouped by their first or second element.

Test cases

inputs               output

"123456", "abcd"     [["1","a"],["1","b"],["1","c"],["1","d"],["2","a"],["2","b"],["2","c"],["2","d"],["3","a"],["3","b"],["3","c"],["3","d"],["4","a"],["4","b"],["4","c"],["4","d"],["5","a"],["5","b"],["5","c"],["5","d"],["6","a"],["6","b"],["6","c"],["6","d"]]
"abc", "123"         [["a","1"],["a","2"],["a","3"],["b","1"],["b","2"],["b","3"],["c","1"],["c","2"],["c","3"]]
"aa", "aba"          [["a","a"],["a","b"],["a","a"],["a","a"],["a","b"],["a","a"]]

@Adám Changed. I'm having trouble though wording that repeated characters in an input string can and should cause repeated pairs in the output (assuming that's how interpret it). — xnor, Jun 8, 2017 at 0:25
Why does the title say "list" yet the body say "list of characters"? — Leaky Nun, Jun 8, 2017 at 7:56
Just to be sure: is ["1a", "1b", "1c", "2a", "2b", "2c", "3a", "3b", "3c"] a valid output format? — Shaggy, Jun 8, 2017 at 16:22
You tagged this as code-golf therefore shortest answer wins. In the event of a tie, the first answer to reach that score is usually the winner (currently this one). Give it another few days, at least, before accepting an answer, though, if at all. And see here for guidelines on answering your own question. — Shaggy, Jun 9, 2017 at 10:52

Neil · Accepted Answer · 2017-09-21 20:28:15Z

1

Charcoal, 8 7 bytes

ＦθＥη⁺ικ

Try it online! Link is to verbose version of code. Explanation: The variables θ and η implicitly refer to the two input strings. The Ｆ command loops over each character of the first input, while the Ｅ command maps over each character of the second input concatenating the loop variable ι and the map variable κ, the result of which is implicitly printed on separate lines.

edited Sep 21, 2017 at 20:28

answered Jun 8, 2017 at 19:14

Neil

166k12 gold badges70 silver badges273 bronze badges

\$\begingroup\$ This seems to be 19 bytes. \$\endgroup\$
– CalculatorFeline
Jun 9, 2017 at 16:44
1

\$\begingroup\$ @CalculatorFeline Charcoal has its own code page. \$\endgroup\$
– Neil
Jun 9, 2017 at 17:03

Add a comment |

JayCe · Accepted Answer · 2018-06-13 15:41:48Z

1

R, 29 bytes

function(x,y)outer(x,y,paste)

Try it online!

Note that R matrix are filled by column, so the result is in the order dictated by the spec.

If allowed to have factors for input and output, there is a built-in... but one needs to extract the resulting levels from the factor so in the end it would be more than 29 bytes.

R, 11 bytes

interaction

Try it online!

answered Jun 13, 2018 at 15:41

JayCe

2,94311 silver badges17 bronze badges

Add a comment |

user85052user85052 · Accepted Answer · 2020-01-26 14:20:24Z

1

GolfScript, 21 bytes

~\:a;{a{[.;1$]}%\;}%`

Try it online!

answered Jan 26, 2020 at 14:20

user85052

Add a comment |

General Grievance · Accepted Answer · 2020-09-21 14:43:08Z

Google Sheets, 101

Inputs A1, B1.

=ArrayFormula(REGEXEXTRACT(Flatten(MID(A1,SEQUENCE(LEN(A1)),1)&MID(B1,SEQUENCE(1,LEN(B1)),1)),"(.)(.)

How it Works

Turn string into character array. The first is vertical, the second is horizontal because of how we call SEQUENCE.
Concatenate every permutation of one letter from each string. (Because one is vertical and the other is horizontal.
Flatten into array
Extract first and second character by Regex
I considered delimiting by commas and splitting, but that would have required more work if the first string had a comma (or whatever delimiting character).

Notes

Flatten is an undocumented function that turns any range into a column array.

user · Accepted Answer · 2020-09-21 15:08:53Z

1

Scala, 24 bytes

for(x<-_;y<-_)yield(x,y)

Try it online!

I love for comprehensions.

answered Sep 21, 2020 at 15:08

user

2872 gold badges20 silver badges68 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2020-09-21 16:30:08Z

1

Add++, 8 bytes

L*,€€+BF

Try it online!

How it works

L*,		; Create an anonymous function that returns the entire stack
		; Example inputs: 	"abc" "123"
	€	; Over each char:	["1" "abc"]
	 €	;   Over each char:	["1" "a"]
	  +	;     Concatenate	"a1"
		;   This returns	["a1" "a2" "a3"]
		; This returns		[[["a1" "a2" "a3"] ["b1" "b2" "b3"] ["c1" "c2" "c3"]]]
	BF	; Flatten		["a1" "a2" "a3" "b1" "b2" "b3" "c1" "c2" "c3"]

answered Sep 21, 2020 at 16:30

caird coinheringaahin g♦

49.5k11 gold badges121 silver badges348 bronze badges

Add a comment |

Pacmanboss256 · Accepted Answer · 2022-10-03 13:09:47Z

1

Vyxal, 1 byte

Π

Try it Online!

Vyxal's built ins are fun!

answered Oct 3, 2022 at 13:09

Pacmanboss256

2,1306 silver badges20 bronze badges

Add a comment |

noodle man · Accepted Answer · 2023-05-06 00:20:45Z

1

JavaScript (ES6), 35 bytes

a=>b=>a.flatMap(x=>b.map(y=>[x,y]))

f=
a=>b=>a.flatMap(x=>b.map(y=>[x,y]))

document.write(`<pre style="font-size: 1rem">${[
  "f([1, 2, 3])(['a', 'b', 'c']) ",
  "f([2, 4, 6, 8])([1, 3, 5, 7]) ",
  "f(['A', 'B'])(['c', 'd', 'e'])",
].map(test => `${test} &rarr; ${JSON.stringify(eval(test))}`).join("\n")}</pre>`)

edited May 6 at 0:20

answered May 5 at 23:57

noodle man

5,5271 gold badge14 silver badges51 bronze badges

Add a comment |

The Thonnu · Accepted Answer · 2023-05-06 13:29:18Z

1

Thunno 2, 1 byte

Ṗ

Built-in. Takes input in reversed order.

Screenshot

answered May 6 at 13:29

The Thonnu

17.8k3 gold badges14 silver badges74 bronze badges

Add a comment |

noodle man · Accepted Answer · 2023-05-06 14:10:55Z

TypeScript Type System, 111 bytes

type X<A,B>=A extends[infer F,...infer R]?[...B extends[any,...infer V]?[[F,B[0]],...X<[F],V>]:[],...X<R,B>]:[]

Test it at the TypeScript playground

My old, more intuitive answer is unfortunately invalid due to the challenge requiring an array of tuples rather than an array of arrays of tuples. This complicated mess, on the other hand, seems to be shorter than using the old version and defining a flatten-type.

type X<A, B> = A extends [ // generic type X takes tuples A and B
  infer F,                 // from A, get first (F)
  ...infer R               // and rest (R)
]
  ? [                                // push:
      ...B extends [any, ...infer V] //   get first and rest (V) from B
        ? [                          //   push:
            [F, B[0]],               //     [ F, B[0] ]
            ...X<[F], V>             //     recurse with [F], V
          ]
        : [],
      ...X<R, B>                     //   recurse with R, B
    ]
  : [];

TypeScript Type System, 57 bytes

This is technically invalid for this specific challenge, but I'm leaving it here since it is more practical for other challenges where cartesian product is used.

type P<A,B>={[I in keyof A]:{[J in keyof B]:[A[I],B[J]]}}

Test it at the TypeScript playground

Pretty simple but I'll leave an explanation anyway for those who don't know any TypeScript:

type P<A, B> = {                 // generic type P takes tuple types A and B
  [I in keyof A]: {              //   for index i in A:
    [J in keyof B]: [A[I], B[J]] //     for index j in B: tuple [A[i], B[j]]
  }                              //   end
}                                // end

Kirill L. · Accepted Answer · 2023-05-08 12:22:07Z

Julia, 21 bytes

a^b=permutedims(a).*b

Attempt This Online!

Takes input as character arrays, returns length-2 strings. Frustratingly, one-byte ' operator doesn't work with text, so we have to permutedims instead. Still a few bytes shorter than a nested for loop.

While this technically returns a 2D matrix, which the OP doesn't want, it does support 1D-indexing (as demonstrated in test cases on ATO), and so is perfectly usable as a flat list. However, this requirement probably invalidates the built-in answer, as Julia flattens the Matrix in column-major order, giving a different result sequence:

Julia, 17 bytes

Iterators.product

Attempt This Online!

\$\begingroup\$ 15 bytes: a^b=[a...;;].*b (needs julia 1.7+) \$\endgroup\$
– MarcMush
May 31 at 15:37 — MarcMush, May 31 at 15:37

mousetail · Accepted Answer · 2023-06-01 13:34:26Z

1

><> (Fish), 92 bytes

fi:?v~:f(?v1-00.
-10.\i{:{:}$}$p1
1~v?gf:11~/.27oa$<v!?ge:+1$
  \:fgo$:ego$1+ $/;

Try it

Each list should be prefixed by it's length

edited Jun 1 at 13:34

answered Jun 1 at 12:56

mousetail

11.8k1 gold badge31 silver badges75 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2023-06-04 04:28:04Z

1

Nekomata, 2 bytes

ᵐ~

Attempt This Online!

ᵐ   Map
 ~  Any of

A port of @Fatalize's Brachylog answer.

edited Jun 4 at 4:28

answered Jun 1 at 5:52

alephalpha

46.7k7 gold badges61 silver badges172 bronze badges

Add a comment |

jq170727 · Accepted Answer · 2017-09-22 04:17:30Z

Jq 1.5, 29 bytes

map(split(""))|[combinations]

Uses combinations builtin.

Sample Run

$ jq -Mc  'map(split(""))|[combinations]' <<< '["123456","abcd"]'
[["1","a"],["1","b"],["1","c"],["1","d"],["2","a"],["2","b"],["2","c"],["2","d"],["3","a"],["3","b"],["3","c"],["3","d"],["4","a"],["4","b"],["4","c"],["4","d"],["5","a"],["5","b"],["5","c"],["5","d"],["6","a"],["6","b"],["6","c"],["6","d"]]

$ echo -n 'map(split(""))|[combinations]' | wc -c
  29

Community · Accepted Answer · 2020-06-17 09:04:33Z

Axiom, 55 bytes

f(a,b)==concat[[[a.x,b.y]for y in 1..#b]for x in 1..#a]

some results

(15) -> f("123456","abcd")
   (15)
   [[1,a], [1,b], [1,c], [1,d], [2,a], [2,b], [2,c], [2,d], [3,a], [3,b],
    [3,c], [3,d], [4,a], [4,b], [4,c], [4,d], [5,a], [5,b], [5,c], [5,d],
    [6,a], [6,b], [6,c], [6,d]]
                                                Type: List List Character
(16) -> f("abc","123")
   (16)  [[a,1],[a,2],[a,3],[b,1],[b,2],[b,3],[c,1],[c,2],[c,3]]
                                                Type: List List Character
(17) -> f("aa","aba")
   (17)  [[a,a],[a,b],[a,a],[a,a],[a,b],[a,a]]
                                                Type: List List Character

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

APL NARS 8 chars

{,⍺∘.,⍵}

Copy from https://codegolf.stackexchange.com/a/125115/58988 test

f←{,⍺∘.,⍵}
'123456' f 'abcd'
 1a 1b 1c 1d 2a 2b 2c 2d 3a 3b 3c 3d 4a 4b 4c 4d 5a 5b 5c 5d 6a 6b 6c 6d

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 17, 2017 at 19:57

user58988

Add a comment |

ASCII-only · Accepted Answer · 2018-05-29 23:35:36Z

0

Prolog (SWI), 48 bytes

L-R:-findall([A,B],(member(A,L),member(B,L)),R).

Try it online!

answered May 29, 2018 at 23:35

ASCII-only

5,11920 silver badges43 bronze badges

Add a comment |

Kip the Malamute · Accepted Answer · 2023-02-01 11:58:49Z

0

Pyt, 1 byte

×

Try it online!

Gotta love built-ins.

answered Feb 1 at 11:58

Kip the Malamute

1,6671 silver badge13 bronze badges

Add a comment |

The Thonnu · Accepted Answer · 2023-02-01 12:28:01Z

0

Thunno, \$ 2 \log_{256}(96) \approx \$ 1.65 bytes

Z!

Attempt This Online!

Thunno, \$ 2 \log_{256}(96) \approx \$ 1.65 bytes

zS

Attempt This Online!

Built-in solutions.

edited Feb 1 at 12:28

answered Feb 1 at 12:04

The Thonnu

17.8k3 gold badges14 silver badges74 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2023-05-28 11:59:20Z

0

Scala, 45 bytes

Golfed version. Try it online!

(a:String,b:String)=>for{x<-a;y<-b}yield(x,y)

answered May 28 at 11:59

138 Aspen

4,8351 gold badge3 silver badges13 bronze badges

Add a comment |

mousetail · Accepted Answer · 2023-05-30 13:25:33Z

0

awk, 101 bytes

it's verbose but doesn't involve cryptic BS

echo '123456 abcd' |

awk 'function ___(_,__) { gsub(".","\\&& ",__)gsub(".",__,_); return _ 
     }$++NF = ___($++_, $++_)'

123456 abcd 1a 1b 1c 1d 2a 2b 2c 2d 3a 3b 3c 3d 4a 4b 4c 4d 5a 5b 5c 5d 6a 6b 6c 6d

edited May 30 at 13:25

mousetail

11.8k1 gold badge31 silver badges75 bronze badges

answered May 8 at 19:22

RARE Kpop Manifesto

3371 silver badge5 bronze badges

Add a comment |

Cartesian product of two lists

Task

Example

Input

Output

Test cases

51 Answers 51

Charcoal, 8 7 bytes

R, 29 bytes

R, 11 bytes

GolfScript, 21 bytes

Google Sheets, 101

How it Works

Notes

Scala, 24 bytes

Add++, 8 bytes

How it works

Vyxal, 1 byte

JavaScript (ES6), 35 bytes

Thunno 2, 1 byte

Screenshot

TypeScript Type System, 111 bytes

TypeScript Type System, 57 bytes

Julia, 21 bytes

Julia, 17 bytes

><> (Fish), 92 bytes

Nekomata, 2 bytes

Jq 1.5, 29 bytes

Axiom, 55 bytes

APL NARS 8 chars

Prolog (SWI), 48 bytes

Pyt, 1 byte

Thunno, \$ 2 \log_{256}(96) \approx \$ 1.65 bytes

Thunno, \$ 2 \log_{256}(96) \approx \$ 1.65 bytes

Scala, 45 bytes

awk, 101 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfset-theory or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
set-theory
or ask your own question.