10
\$\begingroup\$

When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n times.

For example, in pseudocode your function could be similar to:

for x1 in list:
    for x2 in list:
        for x3 in list:
            ...
            for xn in list:
                print x1, x2, x3, ... , xn

Example:

repeated_cart([1,2,3], 3)

1 1 1  
1 1 2  
1 1 3  
1 2 1  
1 2 2  
1 2 3  
1 3 1  
1 3 2  
1 3 3  
2 1 1  
2 1 2  
2 1 3  
2 2 1  
2 2 2  
2 2 3  
2 3 1  
2 3 2  
2 3 3  
3 1 1  
3 1 2  
3 1 3  
3 2 1  
3 2 2  
3 2 3  
3 3 1  
3 3 2  
3 3 3

Built in functions (or functions from imported libraries) that compute the Cartesian product (or power) are not allowed due to the resulting code being somewhat boring.

Inputs and outputs should be delimited but can be taken in any reasonable method.

the order the output is given does not matter but duplicates are not allowed.

This is my first time posting a question, so if I did anything horribly wrong, please tell me.

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to PPCG! Nothing horribly wrong, but take some time to look at this meta post and answers.Things to avoid when writing challenges \$\endgroup\$ – JayCe May 29 '18 at 18:37
  • 4
    \$\begingroup\$ and to follow on @JayCe 's point, you could (should) post in The Sandbox to get feedback before posting a question :-) \$\endgroup\$ – Giuseppe May 29 '18 at 18:40
  • \$\begingroup\$ @Giuseppe Ok, I'll do that from now on, thanks :) \$\endgroup\$ – JoshM May 29 '18 at 18:47
  • 1
    \$\begingroup\$ Borderline dupe of codegolf.stackexchange.com/q/125104/194 \$\endgroup\$ – Peter Taylor May 29 '18 at 19:14
  • 1
    \$\begingroup\$ @Jakob sets should be fine \$\endgroup\$ – JoshM May 30 '18 at 1:24

22 Answers 22

8
\$\begingroup\$

Haskell, 21 bytes

l#n=mapM(\_->l)[1..n]

Try it online!

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

Common Lisp, 146 bytes

(defun f(l n)(if(< n 2)(loop for x in l collect(list x))(loop for a in l nconc(loop for b in(f l(1- n))collect(cons a b)))))(princ(f(read)(read)))

Try it online!

ungolfed

(defun nloops (lst n)
  (if (< n 1)
      '(())
      (if (< n 2)
          (loop for x in lst collect (list x))
          (loop for a in lst
                nconc (loop for b in (nloops lst (1- n))
                            collect (cons a b))))))
\$\endgroup\$
  • 2
    \$\begingroup\$ typically we suggest waiting for other submissions before posting one of your own :-) \$\endgroup\$ – Giuseppe May 29 '18 at 18:33
  • 1
    \$\begingroup\$ @Giuseppe Ok, thanks for the advice :) \$\endgroup\$ – JoshM May 29 '18 at 18:47
  • 1
    \$\begingroup\$ you don't have to have the print statement in the submission, since a function is allowed \$\endgroup\$ – ASCII-only Jun 1 '18 at 11:07
  • 1
    \$\begingroup\$ so: 96 \$\endgroup\$ – ASCII-only Jun 1 '18 at 11:22
  • 1
    \$\begingroup\$ 90 \$\endgroup\$ – ASCII-only Jun 1 '18 at 11:26
6
\$\begingroup\$

R, 41 bytes

function(l,n)unique(t(combn(rep(l,n),n)))

Try it online!

combn is definitely not a cartesian product built-in, as it computes all n-combinations of its input.

R, 40 bytes

function(l,n)expand.grid(rep(list(l),n))

Try it online!

expand.grid is probably a cartesian product built-in.

\$\endgroup\$
  • \$\begingroup\$ Looks like the order of permutations in your main submission is wrong. \$\endgroup\$ – Kirill L. May 30 '18 at 9:01
  • \$\begingroup\$ @KirillL. is there a particular reason the order is important? I interpreted the output spec as being flexible enough to allow them in any order. \$\endgroup\$ – Giuseppe May 30 '18 at 16:34
  • \$\begingroup\$ there is OP's comment "make sure the output is in the right order", I presumed "right" means same as in example. \$\endgroup\$ – Kirill L. May 30 '18 at 16:46
  • \$\begingroup\$ @KirillL. Ah. Didn't see that; it's not in the body of the question so I did not know it existed! I'll ask that it gets put there for clarification. \$\endgroup\$ – Giuseppe May 30 '18 at 17:12
4
\$\begingroup\$

Perl 6, 16 bytes

{[X,] $^a xx$^b}

Try it

Expnded:

{  # bare block lambda with placeholder parameters $a and $b

  [X,]         #reduce using Cross meta op combined with comma op

    $^a xx $^b # list repeat $a, by $b times
}
\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 10 bytes

{x@+!y##x}

Try it online!

{ } is a function with arguments x and y

#x the length of x

y##x the length of x repeated y times

!y##x all length-y tuples over 0,1,...,length(x)-1 as a transposed matrix

+ transpose

x@ elements of x at those indices

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

APL (Dyalog Classic), 18 12 bytes

{⍺[↑,⍳⍵⍴≢⍺]}

Try it online!

-6 bytes thanks to @ngn !

\$\endgroup\$
  • \$\begingroup\$ you can use with a vector argument to generate indices and then ⍺[ ] to get the corresponding values \$\endgroup\$ – ngn May 29 '18 at 19:35
  • \$\begingroup\$ I got a RANK ERROR when I tried to do that. \$\endgroup\$ – Zacharý May 29 '18 at 19:40
  • \$\begingroup\$ ⍺[↑,⍳⍵⍴≢⍺] \$\endgroup\$ – ngn May 29 '18 at 19:48
  • \$\begingroup\$ the only catch is with ⍵=1, in that case ⍳ returns a plain vector, not a vector of nested length-1 vectors as one would expect; it's one of those bugs that never get fixed, for backwards-compatibility reasons \$\endgroup\$ – ngn May 29 '18 at 19:56
3
\$\begingroup\$

Perl 5, 33 bytes

say for glob(join',',("{$_}")x<>)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice! So many answers have been able to utilise this lately! You can save 2 bytes with a bit of juggling: Try it online! \$\endgroup\$ – Dom Hastings May 29 '18 at 20:24
3
\$\begingroup\$

Python 2, 69 58 bytes

f=lambda a,n:n and[v+[i]for v in f(a,n-1)for i in a]or[[]]

Try it online!

Takes a list a and an integer n; returns a list of lists.

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

Ruby, 53 bytes

f=->l,n{n<2?l:l.flat_map{|i|f[l,n-1].map{|j|[i,*j]}}}

Try it online!

Recursive approach, not so short, but guaranteed to be free of any built-ins.

It's tempting to use permutation methods, but this probably doesn't count, and the docs actually state no guarantees of the order correctness, although seems to work in practice:

Ruby, 35 bytes

->l,n{[*l.repeated_permutation(n)]}

Try it online!

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

Prolog (SWI), 72 bytes

R-1-R.
L-N-R:-O is N-1,L-O-M,findall([H|T],(member(H,L),member(T,M)),R).

Try it online!

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

Racket, 92 bytes

(define(f l n)(if(> n 0)(apply append(map(λ(r)(map(λ(e)(cons e r))l))(f l(- n 1))))'(())))

Try It Online

Ungolfed

(define (f l n)
    (if (> n 0)
        (apply append
            (map
                (λ (r)
                    (map (λ (e) (cons e r)) l)
                )
                (f l (- n 1))
            )
        )
        '(())
    )
)
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 9 7 bytes

³;þẎƊ’¡

Try it online!

Explanation

³;þẎƊ’¡
³;þẎ    **Implements** the cartesian product of a value with the input
    Ɗ   Groups those together
     ’¡ Repeat (n-1) times
\$\endgroup\$
  • \$\begingroup\$ Look at OP's comment :p \$\endgroup\$ – Zacharý May 29 '18 at 18:43
  • \$\begingroup\$ My comment to which I brought it up is: "I'm also assuming builtins for the entire challenge are also disalowed," so I just assumed this is okay. \$\endgroup\$ – Zacharý May 29 '18 at 18:45
  • \$\begingroup\$ Well, let's wait for OP then \$\endgroup\$ – Zacharý May 29 '18 at 18:49
  • \$\begingroup\$ @Zacharý sorry, the cartesian power function isn't allowed \$\endgroup\$ – JoshM May 29 '18 at 19:03
  • 3
    \$\begingroup\$ I don't know, two nested for loops like that is basically the definition of a cartesian product. I'm not saying you should change it though, I just think banning the built-in in this challenge is kind of unclear. \$\endgroup\$ – dylnan May 29 '18 at 19:47
2
\$\begingroup\$

Pure Bash (no external utilities), 57

printf -vn %0$1d
a=${n//0/{$2\}}
eval echo ${a//\}{/\},{}

Input is given as command-line parameters; 1st is n, 2nd is a comma-separated list.

printf -vn %0$1d         ;# Create a string of n "0"s in the variable v
a=${n//0/{$2\}}          ;# Replace each "0" with "{a,b,...m}"
eval echo ${a//\}{/\},{} ;# Replace each "}{" with "},{" and evaluate the resulting brace expansion

Try it online!

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

Java 10, 19 + 135 = 154 bytes

import java.util.*;

List<List>f(Set l,int n){var o=new Stack();if(n<1)o.add(new Stack());else for(var t:l)for(var i:f(l,n-1)){i.add(t);o.add(i);}return o;}

Try It Online

Ungolfed

List<List> f(Set l, int n) {
    var o = new Stack();
    if (n < 1)
        o.add(new Stack());
    else
        for (var t : l)
            for (var i : f(l, n - 1)) {
                i.add(t);
                o.add(i);
            }
    return o;
}

Acknowledgments

  • port to Java 10 thanks to Kevin Cruijssen
\$\endgroup\$
  • \$\begingroup\$ If you use Java 10 instead of 8, you can change Object and List in the for-each loops to var for -4 bytes. In addition, you can then change Set<List>f to List<List>f and Set o=new HashSet(); to var o=new Stack(); for an additional -1 byte. Try it online. \$\endgroup\$ – Kevin Cruijssen May 30 '18 at 7:08
  • \$\begingroup\$ Hmm. is leaving out types for lambdas no longer valid \$\endgroup\$ – ASCII-only May 31 '18 at 12:37
  • \$\begingroup\$ @ASCII-only No, untyped lambdas are allowed. I couldn't use a lambda here because the solution uses recursion. \$\endgroup\$ – Jakob May 31 '18 at 19:12
  • \$\begingroup\$ @Jakob ah, that's right >_> \$\endgroup\$ – ASCII-only Jun 1 '18 at 0:58
2
\$\begingroup\$

Oracle SQL, 177 bytes

Create a collection type (31 bytes):

CREATE TYPE t IS TABLE OF INT;

Then use the query (146 bytes):

WITH n(a,b,c)AS(SELECT a,b,t()FROM i UNION ALL SELECT a,b-1,c MULTISET UNION t(COLUMN_VALUE)FROM n,TABLE(n.a)WHERE b>=0)SELECT c FROM n WHERE b=0

Assuming that the input parameters are in the table i with columns a and b:

CREATE TABLE i (a t,b INT) NESTED TABLE a STORE AS t_a;
INSERT INTO i VALUES ( t(1,2,3), 3 );

SQL Fiddle

Results:

|     C |
|-------|
| 1,1,1 |
| 1,1,2 |
| 1,1,3 |
| 1,2,1 |
| 1,2,2 |
| 1,2,3 |
| 1,3,1 |
| 1,3,2 |
| 1,3,3 |
| 2,1,1 |
| 2,1,2 |
| 2,1,3 |
| 2,2,1 |
| 2,2,2 |
| 2,2,3 |
| 2,3,1 |
| 2,3,2 |
| 2,3,3 |
| 3,1,1 |
| 3,1,2 |
| 3,1,3 |
| 3,2,1 |
| 3,2,2 |
| 3,2,3 |
| 3,3,1 |
| 3,3,2 |
| 3,3,3 |
\$\endgroup\$
1
\$\begingroup\$

Bash, 61 bytes

N=$1
shift
IFS=,
printf echo\\t%${N}s ""|sed "s/ /{$*},/g"|sh

Try it online! I found repeating strings and joining lists with commas surprisingly hard to do in bash.

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

Javascript (Node), 75 bytes

c=(m,n,a,i)=>a.length-n?m.map((_,j)=>c(m,n,[...a,m[j]],i+1)):console.log(a)

Recursive function which outputs the list to the console. Where a is an empty array and i is 0 (not sure if this still qualifies):

c([1,2,3], 3, [], 0);

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you would have to do (m,n,a=[],i=0)=> \$\endgroup\$ – Artyer May 30 '18 at 8:51
1
\$\begingroup\$

JavaScript (SpiderMonkey), 52 bytes

c=>g=(n,...l)=>n?c.map(w=>g(n-1,...l,w)):print(...l)

Try it online!

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

J, 17 bytes

]{~(##)#:#@]i.@^[

How it works?

I enumerate all the n-digit numbers in a number system with base the length of the list.

            i.         - creates a list from zero to (not including)
         #@]           - the length of the list 
              @^       - to the power of
                [      - n (left argument)
   (##)                - creates a list of n times the length of the list (for the bases)
       #:              - converts all the numbers into lists of digits in the new base
]{~                    - use the digits as indices into the list

Try it online!

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

CJam, 26 bytes

q~(_"m*:e_"*\'_*@\~W$~:p];

Try it online!

If only CJam had one character commands for cartesian product and flattening.

\$\endgroup\$
0
\$\begingroup\$

Octave, 38 bytes

@(x,n)x(dec2base(0:n^numel(x)-1,n)-47)

Anonymous function that takes a row vector of values and an integer.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 46 bytes

(l,n)->matrix(#l^n,n,i,j,l[i--\#l^(n-j)%#l+1])

Try it online!

\$\endgroup\$

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.