Cartesian product of a list with itself n times

Question

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.

Answer 1

Haskell, 21 bytes

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

Try it online!

Answer 2

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

Answer 3

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.

Answer 4

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
}

Answer 5

APL (Dyalog Classic), 18 12 bytes

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

Try it online!

-6 bytes thanks to @ngn !

Answer 6

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

Answer 7

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.

Answer 8

Perl 5, 33 bytes

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

Try it online!

Answer 9

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!

Answer 10

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

Answer 11

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!

Answer 12

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

Answer 13

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

Answer 14

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!

Answer 15

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 |

Answer 16

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.

Answer 17

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!

Answer 18

JavaScript (SpiderMonkey), 52 bytes

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

Try it online!

Answer 19

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!

Answer 20

CJam, 26 bytes

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

Try it online!

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

Answer 21

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!

Answer 22

Pari/GP, 46 bytes

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

Try it online!