# Cartesian product of a list with itself n times

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

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

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


Try it online!

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

• Looks like the order of permutations in your main submission is wrong. May 30, 2018 at 9:01
• @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. May 30, 2018 at 16:34
• there is OP's comment "make sure the output is in the right order", I presumed "right" means same as in example. May 30, 2018 at 16:46
• @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. May 30, 2018 at 17:12

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

• typically we suggest waiting for other submissions before posting one of your own :-) May 29, 2018 at 18:33
• @Giuseppe Ok, thanks for the advice :) May 29, 2018 at 18:47
• you don't have to have the print statement in the submission, since a function is allowed Jun 1, 2018 at 11:07
• so: 96 Jun 1, 2018 at 11:22
• 90 Jun 1, 2018 at 11:26

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


# 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

# APL (Dyalog Classic), 18 12 bytes

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


Try it online!

-6 bytes thanks to @ngn !

• you can use ⍳ with a vector argument to generate indices and then ⍺[ ] to get the corresponding values
– ngn
May 29, 2018 at 19:35
• I got a RANK ERROR when I tried to do that. May 29, 2018 at 19:40
• ⍺[↑,⍳⍵⍴≢⍺]
– ngn
May 29, 2018 at 19:48
• 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
– ngn
May 29, 2018 at 19:56

# Perl 5, 33 bytes

say for glob(join',',("{$_}")x<>)  Try it online! • Nice! So many answers have been able to utilise this lately! You can save 2 bytes with a bit of juggling: Try it online! May 29, 2018 at 20:24 # 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. # 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! # 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! # 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)) ) ) '(()) ) )  # Jelly, 119 7 bytes ³;þẎƊ’¡  Try it online! ## Explanation ³;þẎƊ’¡ ³;þẎ **Implements** the cartesian product of a value with the input Ɗ Groups those together ’¡ Repeat (n-1) times  • Look at OP's comment :p May 29, 2018 at 18:43 • 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. May 29, 2018 at 18:45 • Well, let's wait for OP then May 29, 2018 at 18:49 • @Zacharý sorry, the cartesian power function isn't allowed May 29, 2018 at 19:03 • 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. May 29, 2018 at 19:47 # 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! # 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 • 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. May 30, 2018 at 7:08 • Hmm. is leaving out types for lambdas no longer valid May 31, 2018 at 12:37 • @ASCII-only No, untyped lambdas are allowed. I couldn't use a lambda here because the solution uses recursion. May 31, 2018 at 19:12 • @Jakob ah, that's right >_> Jun 1, 2018 at 0:58 # 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 | 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 |  # 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. # 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! • >@,@{@(#<) for 10. You can remove the >@ for 8 if boxed output is acceptable. Try it online! Jul 3, 2021 at 19:52 • @Jonah Thank you! Jul 4, 2021 at 7:26 # 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! # 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.

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

• I think you would have to do (m,n,a=[],i=0)=> May 30, 2018 at 8:51

# JavaScript (SpiderMonkey), 52 bytes

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


Try it online!

# CJam, 26 bytes

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


Try it online!

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

# Pyth, 5 bytes

.nM**


Try it online!

# Vyxal, 5 bytes

ẋf⁰↔U


Try it Online!

# Pari/GP, 46 bytes

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


Try it online!