11
\$\begingroup\$

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 so shortest answer in bytes wins!

\$\endgroup\$
  • 6
    \$\begingroup\$ boring answer: itertools.product in python \$\endgroup\$ – Quintec Nov 16 at 17:54
  • \$\begingroup\$ Related, related. \$\endgroup\$ – Digital Trauma Nov 16 at 23:13
  • 2
    \$\begingroup\$ If your language has no method of stdin, you may take input from command line arguments or a variable I suggest you allow command-line inputs without any condition. See here \$\endgroup\$ – Luis Mendo Nov 17 at 3:12
  • \$\begingroup\$ Does order matter among the output lists? \$\endgroup\$ – xnor Nov 17 at 5:45
  • 1
    \$\begingroup\$ No, the format described is not mandatory @KevinCruijssen \$\endgroup\$ – sugarfi Nov 18 at 22:09

23 Answers 23

12
\$\begingroup\$

J, 1 byte

Courtesy of ngn

{

Try it online!

'tis called Catalogue

\$\endgroup\$
  • \$\begingroup\$ You beat me to it :). I think ,@{ would be more fair though, since the output of naked { doesn't have a uniform structure (ie, it depends on the inputs). \$\endgroup\$ – Jonah Nov 16 at 19:40
  • \$\begingroup\$ @Jonah Jelly gives the same structure. \$\endgroup\$ – Adám Nov 16 at 19:45
  • \$\begingroup\$ results not seem list deep 1 of element of input \$\endgroup\$ – RosLuP Nov 17 at 7:04
  • \$\begingroup\$ @RosLuP It is. J's Try it online! L. is APL's . \$\endgroup\$ – Adám Nov 17 at 7:24
8
\$\begingroup\$

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!

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

Haskell, 23 bytes

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

Try it online!

Without using mapM or sequence or the like.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Since the return value doesn't matter, you can shave two bytes off by using def: Try it online! \$\endgroup\$ – Unrelated String Nov 17 at 6:09
  • 1
    \$\begingroup\$ @ChasBrown I don't think that's allowed, it nests the output a lot. And unfortunately Python doesn't do iterable unpacking in comprehensions. \$\endgroup\$ – xnor Nov 17 at 9:11
  • 1
    \$\begingroup\$ @xnor : quite right! Carry on... \$\endgroup\$ – Chas Brown Nov 17 at 9:12
4
\$\begingroup\$

K (oK), 31 15 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ How are you finding K compared with J? What have you been using to learn it? \$\endgroup\$ – Jonah Nov 17 at 16:36
  • 1
    \$\begingroup\$ @Jonah I can't compare them directly. K lacks J's math capabilities, but works on heterogeneous lists. It is much more compact and I like it very much even I have only sctratched the surface. I started learning from the oK Manual. On several occasions ngn helped me in thr k tree. He also supplied almost all my previos k submissions with golfing tips. \$\endgroup\$ – Galen Ivanov Nov 17 at 19:31
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 59 bytes \$\endgroup\$ – ovs Nov 17 at 13:43
4
\$\begingroup\$

Japt -R, 2 bytes

A simple reduction by Cartesian product.

Try it

\$\endgroup\$
  • \$\begingroup\$ Lol! Congrats! You preceded me by 12 minutes ! Anyway I'm really proud of .. I immediately thought about that solution \$\endgroup\$ – AZTECCO Nov 16 at 21:34
  • \$\begingroup\$ Ha, I spent 15 minutes looking through Japt docs and couldn't find this again. Lol \$\endgroup\$ – Quintec Nov 17 at 14:32
  • \$\begingroup\$ @KevinCruijssen, here it is "pretty printed": petershaggynoble.github.io/Japt-Interpreter/… \$\endgroup\$ – Shaggy Nov 18 at 12:39
  • \$\begingroup\$ OP stated the output-format is indeed flexible, and those outputs are allowed. \$\endgroup\$ – Kevin Cruijssen Nov 19 at 7:08
  • 1
    \$\begingroup\$ Thanks, @KevinCruijssen. I've updated to Japt -R anyway. \$\endgroup\$ – Shaggy Nov 19 at 10:43
3
\$\begingroup\$

Jelly, 4 2 bytes

Œp

Try it online!

Output is "pretty printed" in the TIO link

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

Ruby, 20 bytes

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

Try it online!

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

Brachylog, 1 byte

Try it online!

A slightly less boring generator solution:

Brachylog, 2 bytes

∋ᵐ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ A careful reading of the rules suggests that function submissions are only allowed to output through return values if printing is impossible, so if that's actually enforced, +1 byte to the first for w, and +2 to the second for ẉ⊥. \$\endgroup\$ – Unrelated String Nov 18 at 21:25
3
\$\begingroup\$

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!

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

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?

\$\endgroup\$
  • \$\begingroup\$ &[X] seems to work in this case. \$\endgroup\$ – nwellnhof Nov 17 at 16:52
  • \$\begingroup\$ @nwellnhof What? But &[+] doesn't work? I don't understand when it does and doesn't work \$\endgroup\$ – Jo King Nov 17 at 20:43
  • 2
    \$\begingroup\$ Seems to be an implementation detail of the infix operators. Some infix operators accept more than two args but it's not a requirement. \$\endgroup\$ – nwellnhof Nov 17 at 22:03
2
\$\begingroup\$

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.

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

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)

\$\endgroup\$
  • \$\begingroup\$ Welcome to the site! Unnamed lambdas are perfectly acceptable here, so you can remove the f= to save two bytes. \$\endgroup\$ – caird coinheringaahing Nov 18 at 13:58
  • \$\begingroup\$ @cairdcoinheringaahing Thank you! I have removed the f=. I'm not sure how to make TIO count this as 44 bytes though ... \$\endgroup\$ – L. F. Nov 18 at 14:03
  • \$\begingroup\$ This should work \$\endgroup\$ – caird coinheringaahing Nov 18 at 14:03
  • \$\begingroup\$ @cairdcoinheringaahing Thanks! Didn't know that the backslash works here. \$\endgroup\$ – L. F. Nov 19 at 11:33
  • \$\begingroup\$ @JoKing Absolutely! Thank you! \$\endgroup\$ – L. F. Nov 19 at 11:33
1
\$\begingroup\$

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!

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

Erlang, 57 bytes

c([]) -> [[]];
c([H|T]) -> [[X|Y] || X <- H, Y <- c(T)].
\$\endgroup\$
1
\$\begingroup\$

Japt, 2 bytes

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

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

Charcoal, 22 bytes

IEΠEθLιEθ§λ÷ιΠ∨E…θμLν¹

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

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

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.

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

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
└∊───────┘
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You don't need to include the f= in the byte count here, and can include it in the header: Example . Also, as expand.grid is a built-in, this is basically 11 bytes as expand.grid returns the function. I think we've scored them as such in the past, though am happy to be corrected by someone with more intimate knowledge of practice. \$\endgroup\$ – CriminallyVulgar Nov 18 at 11:57
1
\$\begingroup\$

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

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!

\$\endgroup\$
  • 5
    \$\begingroup\$ You don't have to do any of the string processing. You could just take input as a list of lists: "Given a number of lists" \$\endgroup\$ – caird coinheringaahing Nov 16 at 18:03
  • 1
    \$\begingroup\$ The heart of this answer is just itertools.product too. \$\endgroup\$ – qwr Nov 17 at 6:13

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.