N-Dimensional Cartesian Product

Question

Introduction

The Cartesian product of two lists is calculated by iterating over every element in the first and second list and outputting points. This is not a very good definition, so here are some examples: the Cartesian product of [1, 2] and [3, 4] is [(1, 3), (1, 4), (2, 3), (2, 4)]. The product of [1] and [2] is [(1, 2)]. However, no one said you could only use two lists. The product of [1, 2], [3, 4], and [5, 6] is [(1, 3, 5), (1, 4, 5), (1, 3, 6), (1, 4, 6), (2, 3, 5), (2, 4, 5), (2, 3, 6), (2, 4, 6)].

Challenge

Given a number of lists, your program must output the Cartesian product of the lists given.

• You can assume that there will always be more than 1 list, and that each list will have the same length. No list will ever be empty. If your language has no method of stdin, you may take input from command line arguments or a variable.
• Your program must output the Cartesian product of all the input lists. If your language has no stdout, you may store output in a variable or as a return value. The output should be a list of lists, or any other iterable type.

Example I/O

Input: [1, 2] [3, 4]
Output: [(1, 3), (1, 4), (2, 3), (2, 4)]

Input: [1, 2] [3, 4] [5, 6]
Output: [(1, 3, 5), (1, 4, 5), (1, 3, 6), (1, 4, 6), (2, 3, 5), (2, 4, 5), (2, 3, 6), (2, 4, 6)]

Input: [1, 2, 3] [4, 5, 6]
Output: [(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]

Rules

This is code-golf so shortest answer in bytes wins!

Answer 1

J, 1 byte

Courtesy of ngn

{

Try it online!

'tis called Catalogue…

Answer 2

Haskell, 7 bytes

mapM id

Try it online!

Built-in, 8 bytes

sequence

Try it online!

Less boring, 33 bytes

Out-golfed by xnor's answer. Go upvote that instead!

f[]=[[]]
f(h:t)=[i:j|i<-h,j<-f t]

Try it online!

Answer 3

Haskell, 23 bytes

foldr((<*>).map(:))[[]]

Try it online!

Without using mapM or sequence or the like.

Answer 4

Python 3, 56 bytes

def f(M,*l):M and[f(M[1:],*l,x)for x in M[0]]or print(l)

Try it online!

No itertools. This is one of those weird functions that prints. Thanks to Unrelated String for -2 bytes with def.

Answer 5

Japt -R, 2 bytes

A simple reduction by Cartesian product.

rï

Try it

Answer 6

Python 2, 60 59 bytes

f=lambda A,*x:[[v]+u for v in A for u in x and f(*x)or[[]]]

Try it online!

1 byte thx to ovs.

Look Ma! No itertools!

Answer 7

K (oK), 31 15 bytes

{x@'/:+!(#:)'x}

Try it online!

Answer 8

Jelly, 4 2 bytes

Œp

Try it online!

Output is "pretty printed" in the TIO link

Answer 9

Ruby, 20 bytes

->i,*j{i.product *j}

Try it online!

Answer 10

Brachylog, 1 byte

ẋ

Try it online!

A slightly less boring generator solution:

Brachylog, 2 bytes

∋ᵐ

Try it online!

Answer 11

Retina, 54 39 32 bytes

This took really long to write (as I tried to golf it too) (unsurprisingly, all the golfing ideas only appeared after I finally posted this). Takes input as a list of strings of alphanumeric characters and underscores (whatever \w matches in your universe), each preceded by a semicolon (I assume characters are as acceptable in Retina as numbers are in everything else; in fact, the challenge never actually specified numbers). Outputs the list of the resulting strings, each preceded by a comma.

^
,
+w`,(\w*)[^;]*;\w*(\w)
,$1$2

Explanation:

^                       match the beginning of the string
,                       add a comma there
+w`,(\w*)[^;]*;\w*(\w)  solve the rest of the problem
,$1$2                   replace with a comma, group 1 and group 2

The third and fourth lines are in a convergence loop (run until no change) (declared by the +). The regular expression in the 3rd line works on lines like , ac, bc, ad, bd;ef;gh and matches all substrings starting at a comma and ending at a character after the first semicolon, where the group 1 is the string after the comma and group 2 is the last character.

Try it online!

Answer 12

Perl 6, 8 4 bytes

&[X]

Try it online!

Simple reduce by cross product. It would be nice if I could return the meta-operator by itself, but I've never figured out how to do that. Turns out it works for cross product?

Answer 13

Zsh, 30 bytes

for l;a=($^a\ ${^${=l}})
<<<$a

Try it online!

Split = and cartesian product ^ for each element. Our base case adds an extra space, which cleanly separates our output lists.

Answer 14

R, 54 47 bytes

f=function(x)split(j<-expand.grid(x),1:nrow(j))

Try it online!

If you consider data.frame rows iterable:

R, 27 bytes

f=function(x)expand.grid(x)

Try it online!

Answer 15

Python 3 (Cython), 46 44 31 bytes

__import__('itertools').product

Try it online!

This doesn't need more explanation, right?

(-13 bytes thanks to Jo King; -2 bytes thanks to caird coinheringaahing)

Answer 16

JavaScript (Node.js), 52 bytes

Returns a list of lists.

f=([a,...b],o=[])=>a?a.flatMap(x=>f(b,[...o,x])):[o]

Try it online!

---

JavaScript (V8), 52 bytes

Prints the results.

f=([a,...b],o)=>a?a.map(x=>f(b,o?o+[,x]:x)):print(o)

Try it online!

Answer 17

Erlang, 57 bytes

c([]) -> [[]];
c([H|T]) -> [[X|Y] || X <- H, Y <- c(T)].

Answer 18

Julia 1.0, 34 bytes

No imports used, iterators in Base has this. It actually makes a lazy form of this, but to print them all it will collect each one.

println.(Iterators.product(l...))

where l is the list of lists.

Answer 19

Japt, 2 bytes

rï

Try it

Reduces input by combination with initial value of 1st element

Duplicate of @Shaggy answer, I was solving this while he just posted the same solution. I hope I can leave my answer too because it's awesome

Answer 20

Charcoal, 22 bytes

ＩＥΠＥθＬιＥθ§λ÷ιΠ∨Ｅ…θμＬν¹

Try it online! Link is to verbose version of code. Explanation:

    θ                   Input list
   Ｅ                    Map over elements
      ι                 Current element
     Ｌ                  Length
  Π                     Product
 Ｅ                      Map over implicit range
        θ               Input list
       Ｅ                Map over elements
          λ             Current element
         §              Cyclically indexed by
            ι           Outer index
           ÷            Integer divide
                 θ      Input list
                …       Truncated to length
                  μ     Inner index
               Ｅ        Map over elements
                    ν   Current element
                   Ｌ    Length
              ∨      ¹  Replace empty list with literal 1
             Π          Product
Ｉ                       Cast to string
                        Implicitly print double-spaced on separate lines

Answer 21

APL(NARS), chars 11, bytes 22

{,↑(∘.,)/⍵}

test for product of sets:

  f←{,↑(∘.,)/⍵}
  ⎕fmt (1 2)(3 4)
┌2────────────┐
│┌2───┐ ┌2───┐│
││ 1 2│ │ 3 4││
│└~───┘ └~───┘2
└∊────────────┘
  ⎕fmt f (1 2)(3 4)
┌4──────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 3│ │ 1 4│ │ 2 3│ │ 2 4││
│└~───┘ └~───┘ └~───┘ └~───┘2
└∊──────────────────────────┘
  ⎕fmt f (1 2)(3 4)(5 6)
┌8──────────────────────────────────────────────────────────────────────┐
│┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐ ┌3─────┐│
││ 1 3 5│ │ 1 3 6│ │ 1 4 5│ │ 1 4 6│ │ 2 3 5│ │ 2 3 6│ │ 2 4 5│ │ 2 4 6││
│└~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘ └~─────┘2
└∊──────────────────────────────────────────────────────────────────────┘
  ≢f (1 2)(3 4)(5 6)
8
  f (⍳3)(4 5 6)
 1 4  1 5  1 6  2 4  2 5  2 6  3 4  3 5  3 6 

  ⎕fmt f (4 5 6)
┌1───────┐
│┌3─────┐│
││ 4 5 6││
│└~─────┘2
└∊───────┘

Answer 22

05AB1E, 3 bytes

.ȉ

Outputs [[a,b],[c,d],[d,e]] in the format [[[a,c],d], [[a,c],e], ...]. To output in the format [[a,[c,d]], [a,[c,e]], ...], replace the » with «.

Try it online or try it online with right- instead of left-reduce.

Explanation:

.»   # (Left-)reduce by (or right-reduce with `.«`):
  â  #  Taking the cartesian product of the two lists
     # (after which the resulting list is output implicitly)

Answer 23

Python 3.8, 136 bytes

import re
from itertools import*
print(list(product(*[[int(i) for i in i.split(', ')] for i in re.findall(r'\[([0-9, ]+)\]',input())])))

Try it online!