14
\$\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

35 Answers 35

7
\$\begingroup\$

05AB1E, 1 byte

â

Try it online!

| improve this answer | |
\$\endgroup\$
17
\$\begingroup\$

Haskell, 12 bytes

(<*>).map(,)

Try it online!

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Mathematica, 12 bytes

Tuples@{##}&

Takes two lists of characters as input.

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

APL (Dyalog), 4 bytes

,∘.,

Try it online!

, flatten

∘. the Cartesian

, concatenation

| improve this answer | |
\$\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!

| improve this answer | |
\$\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
4
\$\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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Jelly, 1 byte

p

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Octave, 32 bytes

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

Try it online!

| improve this answer | |
\$\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}
| improve this answer | |
\$\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>

| improve this answer | |
\$\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
3
\$\begingroup\$

Bash, 18

This can be done with brace expansions:

eval echo {$1}{$2}

Try it online.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 5 bytes

{∋ᵐ}ᶠ

Try it online!

Explanation

Pretty self-explanatory

{  }ᶠ       Find all:
  ᵐ           Map:
 ∋              In
| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pyth, 3 bytes

*ww

Multiplying two strings just acts as the cartesian product.

Test it online!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Actually, 1 byte

Try it online!

is the Cartesian product command.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Ohm, 1 byte

Try it online!

Literally only the built-in

| improve this answer | |
\$\endgroup\$
2
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 63 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Clojure, 21 bytes

#(for[i % j %2][i j])
| improve this answer | |
\$\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!

| improve this answer | |
\$\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
| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 bytes

v²NFÀ}¹ø)˜

Try it online!

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

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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\$

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!

| improve this answer | |
\$\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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C# 7, 78 63 bytes

(a,b)=>$"({string.Join(",",a.SelectMany(x=>b,(x,y)=>(x,y)))})";
| improve this answer | |
\$\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.