text:
Cartesian product of two lists
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 maybe easier if the order of pairs is fixed?

Why does the title say "list" yet the body say "list of characters"?

Just to be sure: is ["1a", "1b", "1c", "2a", "2b", "2c", "3a", "3b", "3c"] a valid output format?

wow. lots of amazing answers. what are the criteria for chosing an accepted answer? And should I give my own answer on es5 (the code that inspired the question in the first place?)

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.

@Adám ty for editing.

@Adám I assume taking the input as boxed in J allowed?

@Jonah I'd think so. That's natural for J.

@Adám, Sorry I thought you were the OP and not just the editor.  But thanks.

05AB1E, 1 byte
â

Try it online!

Haskell, 12 bytes
(<*>).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

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])

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

Try it online!

Brachylog, 5 bytes
{∋ᵐ}ᶠ

Try it online!
Explanation
Pretty self-explanatory
{  }ᶠ       Find all:
  ᵐ           Map:
 ∋              In

Jelly, 1 byte
p

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.

It is a shame browsers dont speak ruby. Such a friendly language..

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.

J, 3 bytes
,@{

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

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]

-1 byte thanks to CalculatorFeline spotting an errant <space>.

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.

Thanks, @Neil; forgot to update that after I changed the method I was using.

Is x+y a valid output format?

@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.

for ( Why is there a space?

D'oh! Don't know how that slipped past me @CalculatorFeline!

It seems you have really taken the hang of es6! I invite you to check out my es5 "answer" on my own challenge (the code that inspired my question). Pls feel free to provide improvement suggestions on it.

@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.

getting an error when i try to run this in the "try it" thingy

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 :( https://pyth.herokuapp.com/?code=%2aE&input=%22cd%22%0A%22ab%22&debug=0

Bash, 18
This can be done with brace expansions:
eval echo {$1}{$2}

Try it online.

Common Lisp, 63 bytes
(lambda(a b)(mapcan(lambda(x)(mapcar(lambda(y)(list x y))b))a))

Try it online!

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

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

You are supposed to write a full program or a function and not snippet.

I just changed it. But many answers on this page aren't full programs or functions. Not sure why this one is singled out.

btw, this is why I don't like code golf.

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.

@sundar I suppose so. Thnx.

Note that some languages used here have pretty compact notation for functions. I see only one answer on this page that clearly isn't a full program or function. It seems to be getting complained about now. I've flagged it too. And yes, PPCG's rules can take a while to get used to. I'm probably still missing some.

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

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

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

Husk, 1 byte
*

Try it online! * does Cartesian products when given two lists.

Rockstar, 81 bytes
listen to X
listen to Y
cut X
while X
roll X in C
cut Y in Z
while Z
say C+roll Z

Try it here (Code will need to be pasted in)

Seems like you answered the wrong challenge

Something weird going on, @TheThonnu, every time I edit one it updates the other, too. I've given up for the day, will try again in the morning.

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.

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.

@CalculatorFeline Charcoal has its own code page.

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

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!

GolfScript, 21 bytes
~\:a;{a{[.;1$]}%\;}%`

Try it online!

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.

Scala, 24 bytes
for(x<-_;y<-_)yield(x,y)

Try it online!
I love for comprehensions.

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"]

Vyxal, 1 byte
Π

Try it Online!
Vyxal's built ins are fun!

TypeScript Type System, 111 bytes
type X=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 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={[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 = {                 // 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

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(`
${[
  "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} → ${JSON.stringify(eval(test))}`).join("\n")}
`)

Thunno 2, 1 byte
Ṗ

Built-in. Takes input in reversed order.
Screenshot

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!

15 bytes: a^b=[a...;;].*b (needs julia 1.7+)

Nekomata, 2 bytes
ᵐ~

Attempt This Online!
ᵐ   Map
 ~  Any of

A port of @Fatalize's Brachylog answer.

><> (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

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

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

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

Prolog (SWI), 48 bytes
L-R:-findall([A,B],(member(A,L),member(B,L)),R).

Try it online!

Pyt, 1 byte
×

Try it online!
Gotta love built-ins.

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.

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

Scala, 45 bytes
Golfed version. Try it online!
(a:String,b:String)=>for{x<-a;y<-b}yield(x,y)


text:
Rooting for Trees With the Right Nodes
Background
A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent of another node u if and only if the path from the root to u goes through v and there is an edge connecting u and v. If node v is the parent of node u, node u is a child of node v.
Task
Write a program or function that, given a positive integer number of nodes and a set of non-negative integer numbers of children each parent has, outputs the number of possible rooted trees with that number of nodes (including the root) and each vertex having a number of children in the set, not counting those trees isomorphic to trees already found.
Two trees are isomorphic if one can be transformed into another by renaming the nodes, or in other words look the same when the nodes are unlabelled.
Examples
We shall represent trees as a 0-indexed list of children per index where 0 represents the root, for example [[1],[2],[]] represents that the root 0 has 1 as a child, node 1 has node 2 as a child, and node 2 has no children.
Inputs n=3 and set = [0,1,2]. This is equal to binary trees with three nodes.
The two possible trees are: [[1],[2],[]] and [[1,2],[],[]]. Because they are identical in structure to the two trees, we count neither [[2],[],[1]] nor [[2,1],[],[]]. There are two trees, so the output is 2 or equivalent.
Here is a visualization:  You can see that the second set of two trees are identical in structure to the first set of two and are thus not counted. Both sets are composed of two trees which have one of the following two structures (the root is the node at the top):

Inputs n=5 and set=[0,2]. The only possible tree is [[1,2],[3,4],[],[],[]]. Note that, for example, [[1,2],[],[3,4],[],[]] and [[1,3],[],[],[2,4],[]] are not counted again because they are isomorphic to the sole tree which is counted. The output is 1 or equivalent.
Here is another visualization:

Clearly, all of the trees are isomorphic, so only one is counted. Here is what the trees look like unlabeled:

Input n=4, set=[0,2]. There are no possible trees because each time children are generated from a node, there are either 0 or 2 more nodes. Clearly, 4 nodes cannot be produced by adding 2 or 0 successively to 1 node, the root. Output: 0 or falsey.
Input/Output
Input and output should be taken in a reasonable format.
Input is a positive integer representing n and a list of non-negative integers representing the set of valid numbers of children.
The output is a non-negative integer corresponding to how many trees can be formed.
Test cases
n ; set ; output
3 ; [0,1,2] ; 2
5 ; [0,2] ; 1
4 ; [0,2] ; 0
3 ; [0,1] ; 1
3 ; [0] ; 0
1 ; [0] ; 1
6 ; [0,2,3] ; 2
7 ; [0,2,3] ; 3

Rules

The set of numbers of children will always include zero.
The root node always counts as a node, even if it has no children (see the 1; [0] test case)
This is code-golf, so shortest code wins.

When you say two trees are isomorphic, you mean as rooted trees, right?

@xnor Yes. The isomorphic definition refers to rooted trees.

Haskell, 120 bytes
_#0=1
i#j=div(i#(j-1)*(i+j-1))j
s!n|let(0?1)0=1;(0?_)_=0;(m?n)c=sum[s!m#j*((m-1)?(n-j*m)$c-j)|j<-[0..c]]=sum$(n-1)?n<$>s

Try it online!
How it works
i#j is i multichoose j.
(m?n)c is the number of n-node trees with c children at the root, each of which has a subtree of at most m nodes.  It’s computed by summation over j, the number of these subtrees that have exactly m nodes.
s!n is the number of n-node trees.  It’s computed by summation over c ∈ s, the number of children at the root.

Pyth, 47 bytes
.N?Nsm*/.P+tyNdd.!d:tN-T*dN-YdhY!|tTYLs:LtbbQyE

Try it online
A port of my Haskell answer, but it’s much faster in Pyth thanks to Pyth’s free automatic memoization.  I had to work around a bug in Pyth’s binomial coefficient builtin, though.

Python, 127 bytes
lambda*x:len(g(*x))
g=lambda n,s,d=0:[[]][n-1:d in s]or[[t]+u for c in range(1,n)for t in g(c,s)for u in g(n-c,s,d+1)if[t]+u>u]

Try it online!
The function g enumerates trees, and the main function counts them.
Each tree is recursively generated by splitting the requiring number of nodes n between c nodes in the first branch t, and n-c nodes in the remaining tree u. For a canonical form up to isomorphism, we require the branches to be sorted in decreasing order, so t must be at most the first element of u is u is non-empty. This is enforced as [t]+u>u.
We count the number of children d so far of the current node. When only one node n=1 is left, is must be the current node and there's no more node for children. If the current number of children d is valid, this level can be finished successfully, so we output a singleton of the one-node tree. Otherwise, we've failed and output the empty list.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes