Cartesian product of two lists

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 '17 at 0:25
• @xnor maybe easier if the order of pairs is fixed?
Jun 8 '17 at 0:28
• Why does the title say "list" yet the body say "list of characters"? Jun 8 '17 at 7:56
• Just to be sure: is ["1a", "1b", "1c", "2a", "2b", "2c", "3a", "3b", "3c"] a valid output format? Jun 8 '17 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. Jun 9 '17 at 10:52

(<*>).map(,)


Try it online!

Mathematica, 12 bytes

Tuples@{##}&


Takes two lists of characters as input.

• Same length: Tuples@*List Alternatively, if arbitrary heads are allowed: Tuples@*f Jun 9 '17 at 16:40

05AB1E, 1 byte

â


Try it online!

APL (Dyalog), 4 bytes

,∘.,


Try it online!

, flatten

∘. the Cartesian

, concatenation

• I don't think flatten is a good description here, since flattening would produce the incorrect result, I think "tighten" or "reduce rank" or something similar should work. (Flattened [1,2]x[1,2] is [1,1,1,2,2,1,2,2]) Sep 24 '17 at 14:03

Octave, 32 bytes

@(a,b)[(a+~b')(:) (b'+~a)(:) '']


Try it online!

Ruby, 30 18 bytes

-12 bytes from Jordan reminding me of a way to use the spec to my advantage!

Takes lists of characters as input.

->a,b{a.product b}


Try it online!

• The specification says the input is "Two lists of characters or strings," so I don't think you need .chars. Jun 8 '17 at 4:09
• It is a shame browsers dont speak ruby. Such a friendly language.. Jun 11 '17 at 2:33

Perl 6, 4 bytes

&[X]


This is just a reference to the built-in cross product operator X. It works on lists of any sort, not just characters.

Jelly, 1 byte

p


Try it online!

Tcl, 60 bytes

proc p x\ y {lmap X $x {lmap Y$y {lappend l $X\$Y}};set l}


Use:

% p {1 2 3} {a 2 2}
{1 a} {1 2} {1 2} {2 a} {2 2} {2 2} {3 a} {3 2} {3 2}


Pyth, 3 bytes

*ww


Multiplying two strings just acts as the cartesian product.

Test it online!

• The 2 Bytes solution *E would require to swap the order of the input strings :( pyth.herokuapp.com/… Jun 8 '17 at 15:44

JavaScript (ES6), 453634 33 bytes

Requires Firefox. Takes both inputs as strings or as arrays of individual characters.

a=>b=>[for(x of a)for(y of b)x+y]


Try It

f=
a=>b=>[for(x of a)for(y of b)x+y]
oninput=_=>console.clear()&console.log(f(i.value)(j.value))
console.log(f(i.value="123456")(j.value="abcd"))
<input id=i><input id=j>

• Destructuring works on strings too.
– Neil
Jun 8 '17 at 15:33
• Thanks, @Neil; forgot to update that after I changed the method I was using. Jun 8 '17 at 15:35
• Is x+y a valid output format?
– Neil
Jun 8 '17 at 16:12
• @Neil: That's what I was originally going to go with but, from the test cases, it appears that wouldn't be valid; rereading the output requirements, though, they seem to indicate that it might be. I'll ask for clarification to be sure. Jun 8 '17 at 16:21
• @alexandros84: Yeah, ES6(+) is essential if you're to stand even a remote chance of being competitive in golf - by the time you've typed function, you've already lost! I'll throw a few pointers on your answer later but, in the meantime, have a look at my original array mapping solution in the edit history; you should be able to just rip that off and replace the arrow functions with "real" functions. Jun 11 '17 at 9:15

Bash, 18

This can be done with brace expansions:

eval echo {$1}{$2}


J, 3 bytes

,@{


This is the Catalogue verb in J. We need to Ravel (,) the result to make it 1 dimensional.

Try it online!

Common Lisp, 63 bytes

(lambda(a b)(mapcan(lambda(x)(mapcar(lambda(y)(list x y))b))a))


Try it online!

Brachylog, 5 bytes

{∋ᵐ}ᶠ


Try it online!

Explanation

Pretty self-explanatory

{  }ᶠ       Find all:
ᵐ           Map:
∋              In


QBIC, 29 bytes

[_l;||[_l;||?_sA,a,1|+_sB,b,1


This prints 2-char strings with all combinations on one line each.

Explanation

   ;      Read in string A$_l | Get its length as b [ | and kick off a FOR-loop from 1 to that [_l;|| Do the same for B$
Note that, while the FOR-loop may pass this code several times, the
'read-from cmd line' is done only once.
?_sA,a,1| PRINT the character from A$at the position of the 'a' loop counter +_sB,a,1 concatenated with the char from B$ at the pos of the 'b' loop counter


MATL, 2 bytes

Z*


* is the general operator for products and the prefix Z makes it the cartesian product and can take two strings as arguments.

Try it online!

Python 2, 39 bytes

lambda x,y:[[i,j]for i in x for j in y]


Try it online!

Alternate solution, 34 30 bytes

-4 bytes thanks to Anders Kaseorg.

There is a built-in for this...

from itertools import*
product

• 30 bytes: from itertools import*;product Jun 8 '17 at 2:30

Actually, 1 byte

∙


Try it online!

∙ is the Cartesian product command.

05AB1E, 10 bytes

v²NFÀ}¹ø)˜


Try it online!

This is without the built-in, and undoubtedly won't be competitive.

• The output For input "aba" "aa" it seems wrong
– user58988
Nov 11 '17 at 6:51

Ohm, 1 byte

╒


Try it online!

Literally only the built-in

Japt, 5 2 bytes

Japt now has a method for the Cartesian product.

Takes input as 2 arrays of character strings.

ïV


Try it

C# 7, 78 63 bytes

(a,b)=>$"({string.Join(",",a.SelectMany(x=>b,(x,y)=>(x,y)))})";  • this isn't a full program nor a function Jun 1 '18 at 12:12 • You are supposed to write a full program or a function and not snippet. Jun 4 '18 at 19:08 • I just changed it. But many answers on this page aren't full programs or functions. Not sure why this one is singled out. Jun 4 '18 at 19:17 • btw, this is why I don't like code golf. Jun 4 '18 at 19:23 • Since this is a function, you can directly return the output string instead of writing it to the screen, I think that saves you ~20 bytes. Jul 12 '18 at 5:46 Husk, 1 byte *  Try it online! * does Cartesian products when given two lists. Clojure, 21 bytes #(for[i % j %2][i j])  PHP, 69 bytes <?foreach($_GET[0]as$x)foreach($_GET[1]as$y)$r[]=[$x,$y];print_r($r);  Try it online! Cheddar, 52 bytes a->b->a.chars.map(i->b.chars.map(i&(+))).reduce((+))  Try it online! Retina, 49 bytes .(?=.*¶(.+))$1$&¶ ¶¶.+ ¶ .(?=.*(.)¶)$1$&¶ ¶.¶ ¶  Try it online! Takes input on separate lines. Explanation: .(?=.*¶(.+))$1$&¶  Each character in the first string generates a separate line prefixed by the second string. ¶¶.+ ¶  The original second string is deleted. .(?=.*(.)¶)$1\$&¶


For each character in the first string, each character in the second string generates a separate line prefixed with the first character.

¶.¶
¶


The left-over characters from the first string are deleted.

q/kdb+, 5 bytes

Solution:

cross           / yup, there's a built-in to do exactly this


Example:

q)"123456"cross"abcd"
"1a"
"1b"
"1c"
"1d"
"2a"
"2b"
"2c"
"2d"
"3a"
"3b"
"3c"
"3d"
"4a"
"4b"
...etc


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.

• This seems to be 19 bytes. Jun 9 '17 at 16:44
• @CalculatorFeline Charcoal has its own code page.
– Neil
Jun 9 '17 at 17:03