12
\$\begingroup\$

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

34 Answers 34

6
\$\begingroup\$

05AB1E, 1 byte

â

Try it online!

\$\endgroup\$
17
\$\begingroup\$

Haskell, 12 bytes

(<*>).map(,)

Try it online!

\$\endgroup\$
7
\$\begingroup\$

Mathematica, 12 bytes

Tuples@{##}&

Takes two lists of characters as input.

\$\endgroup\$
  • 1
    \$\begingroup\$ Same length: Tuples@*List Alternatively, if arbitrary heads are allowed: Tuples@*f \$\endgroup\$ – CalculatorFeline Jun 9 '17 at 16:40
4
\$\begingroup\$

APL (Dyalog), 4 bytes

,∘.,

Try it online!

, flatten

∘. the Cartesian

, concatenation

\$\endgroup\$
  • \$\begingroup\$ 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]) \$\endgroup\$ – Zacharý Sep 24 '17 at 14:03
4
\$\begingroup\$

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!

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

Jelly, 1 byte

p

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Octave, 32 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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}
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 45 36 34 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>

\$\endgroup\$
  • \$\begingroup\$ Destructuring works on strings too. \$\endgroup\$ – Neil Jun 8 '17 at 15:33
  • \$\begingroup\$ Thanks, @Neil; forgot to update that after I changed the method I was using. \$\endgroup\$ – Shaggy Jun 8 '17 at 15:35
  • \$\begingroup\$ Is x+y a valid output format? \$\endgroup\$ – Neil Jun 8 '17 at 16:12
  • \$\begingroup\$ @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. \$\endgroup\$ – Shaggy Jun 8 '17 at 16:21
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Shaggy Jun 11 '17 at 9:15
2
\$\begingroup\$

Brachylog, 5 bytes

{∋ᵐ}ᶠ

Try it online!

Explanation

Pretty self-explanatory

{  }ᶠ       Find all:
  ᵐ           Map:
 ∋              In
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 3 bytes

*ww

Multiplying two strings just acts as the cartesian product.

Test it online!

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

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!

\$\endgroup\$
2
\$\begingroup\$

Actually, 1 byte

Try it online!

is the Cartesian product command.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Ohm, 1 byte

Try it online!

Literally only the built-in

\$\endgroup\$
2
\$\begingroup\$

Bash, 18

This can be done with brace expansions:

eval echo {$1}{$2}

Try it online.

\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 63 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Clojure, 21 bytes

#(for[i % j %2][i j])
\$\endgroup\$
1
\$\begingroup\$

PHP, 69 bytes

<?foreach($_GET[0]as$x)foreach($_GET[1]as$y)$r[]=[$x,$y];print_r($r);

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 30 bytes: from itertools import*;product \$\endgroup\$ – Anders Kaseorg Jun 8 '17 at 2:30
1
\$\begingroup\$

Cheddar, 52 bytes

a->b->a.chars.map(i->b.chars.map(i&(+))).reduce((+))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 bytes

v²NFÀ}¹ø)˜

Try it online!

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

\$\endgroup\$
  • \$\begingroup\$ The output For input "aba" "aa" it seems wrong \$\endgroup\$ – RosLuP Nov 11 '17 at 6:51
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 8 7 bytes

FθEη⁺ικ

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.

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

J, 3 bytes

,@{

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Japt, 5 2 bytes

Japt now has a method for the Cartesian product.

Takes input as 2 arrays of character strings.

ïV

Try it

\$\endgroup\$
1
\$\begingroup\$

C# 7, 78 63 bytes

(a,b)=>$"({string.Join(",",a.SelectMany(x=>b,(x,y)=>(x,y)))})";
\$\endgroup\$
  • \$\begingroup\$ this isn't a full program nor a function \$\endgroup\$ – ASCII-only Jun 1 '18 at 12:12
  • \$\begingroup\$ You are supposed to write a full program or a function and not snippet. \$\endgroup\$ – Muhammad Salman Jun 4 '18 at 19:08
  • \$\begingroup\$ I just changed it. But many answers on this page aren't full programs or functions. Not sure why this one is singled out. \$\endgroup\$ – Dennis_E Jun 4 '18 at 19:17
  • \$\begingroup\$ btw, this is why I don't like code golf. \$\endgroup\$ – Dennis_E Jun 4 '18 at 19:23
  • \$\begingroup\$ 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. \$\endgroup\$ – sundar - Reinstate Monica Jul 12 '18 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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