# 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 – JayCe May 29 '18 at 18:37
• and to follow on @JayCe 's point, you could (should) post in The Sandbox to get feedback before posting a question :-) – Giuseppe May 29 '18 at 18:40
• @Giuseppe Ok, I'll do that from now on, thanks :) – JoshM May 29 '18 at 18:47
• Borderline dupe of codegolf.stackexchange.com/q/125104/194 – Peter Taylor May 29 '18 at 19:14
• @Jakob sets should be fine – JoshM May 30 '18 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. – Kirill L. May 30 '18 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. – Giuseppe May 30 '18 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. – Kirill L. May 30 '18 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. – Giuseppe May 30 '18 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 :-) – Giuseppe May 29 '18 at 18:33
• @Giuseppe Ok, thanks for the advice :) – JoshM May 29 '18 at 18:47
• you don't have to have the print statement in the submission, since a function is allowed – ASCII-only Jun 1 '18 at 11:07
• so: 96 – ASCII-only Jun 1 '18 at 11:22
• 90 – ASCII-only Jun 1 '18 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 '18 at 19:35
• I got a RANK ERROR when I tried to do that. – Adalynn May 29 '18 at 19:40
• ⍺[↑,⍳⍵⍴≢⍺] – ngn May 29 '18 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 '18 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! – Dom Hastings May 29 '18 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 – Adalynn May 29 '18 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. – Adalynn May 29 '18 at 18:45 • Well, let's wait for OP then – Adalynn May 29 '18 at 18:49 • @Zacharý sorry, the cartesian power function isn't allowed – JoshM May 29 '18 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. – dylnan May 29 '18 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. – Kevin Cruijssen May 30 '18 at 7:08 • Hmm. is leaving out types for lambdas no longer valid – ASCII-only May 31 '18 at 12:37 • @ASCII-only No, untyped lambdas are allowed. I couldn't use a lambda here because the solution uses recursion. – Jakob May 31 '18 at 19:12 • @Jakob ah, that's right >_> – ASCII-only Jun 1 '18 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! – Jonah Jul 3 at 19:52 • @Jonah Thank you! – Galen Ivanov Jul 4 at 7:26 # 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)=> – Artyer May 30 '18 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.

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

# Pari/GP, 46 bytes

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


Try it online!