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 Cartesian 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 code-golf so shortest code wins

Answer 1

Haskell, 21 bytes

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

Try it online!

Answer 2

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 3

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

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 6

APL (Dyalog Classic), 18 12 bytes

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

Try it online!

-6 bytes thanks to @ngn !

Answer 7

Perl 5, 33 bytes

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

Try it online!

Answer 8

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 9

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 10

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 11

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 12

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 13

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 14

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

Jelly, 5 bytes

ẋœ!ṛQ

Try it online!

Completely different method to Adalynn's existing answer, plus two bytes shorter, so I thought I'd post a separate answer.

The Footer in the TIO link simply runs the above link then checks to see if the result is the same as the Cartesian power builtin. Remove it to see the full output

Same as the old version is length, but more tacit.

How it works

ẋœ!ṛQ - Main link. Takes a list l on the left and n on the right
ẋ     - Repeat l n times; Call this m
   ṛ  - Right; Yield the right argument n
 œ!   - Yield all permutations of m of length n
    Q - Remove duplicates

The previous answer, ẋ⁹œ!Q used a 2-0, 2, 1 chain, where the ⁹ was necessary to prevent the œ! chaining to the ẋ. In this version, we have a 2, 2, 2, 1 chain. As it is at the start of the chain, the special 2,2,2 pattern is matched, meaning we execute the first three dyads, then deduplicate whatever that results in.

For three dyads x (f g h) y, we calculate (x f y) g (x h y) with this 2,2,2 pattern. f here is ẋ, meaning we repeat the list in x y times. h is ṛ, which takes two arguments and returns the right one y. Therefore, we're passing the repeated list to œ! on the left and y on the right, thus getting the permutations of length y.

Answer 17

J, 17 10 bytes

-7 bytes thanks to Jonah!

>@,@{@(#<)

Try it online!

Original soluton:

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 18

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 19

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 20

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 21

JavaScript (SpiderMonkey), 52 bytes

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

Try it online!

Answer 22

CJam, 26 bytes

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

Try it online!

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

Answer 23

Pyth, 5 bytes

.nM**

Try it online!

Answer 24

Vyxal, 5 bytes

ẋf⁰↔U

Try it Online!

Answer 25

Pari/GP, 46 bytes

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

Try it online!