# Cartesian LCM of two arrays

Given two nonempty arrays of natural numbers $$\a\$$ and $$\b\$$, return the shortest nonempty array of pairs of natural numbers $$\q\$$ such that the sequence of first elements of $$\q\$$ consists of a whole number of repeated copies of $$\a\$$, and the sequence of second elements of $$\q\$$ consists of a whole number of repeated copies of $$\b\$$.

When $$\a\$$ and $$\b\$$ have the same length, this acts like a zip, but when the lengths of $$\a\$$ and $$\b\$$ are coprime, this acts like a Cartesian product.

You can use any reasonable input and output format for arrays (pointers, lists, space-separated strings, strings of char codes, etc.)

This is , so the shortest valid answer (measured in bytes) wins.

## Test Cases

[1],          [2]       -> [(1, 2)]
[1, 2],       [3]       -> [(1, 3), (2, 3)]
[1, 2],       [3, 4]    -> [(1, 3), (2, 4)]
[1, 2, 3, 4], [5, 6]    -> [(1, 5), (2, 6), (3, 5), (4, 6)]
[5, 5, 5],    [5, 5, 5] -> [(5, 5), (5, 5), (5, 5)]
[5, 5],       [5, 5, 5] -> [(5, 5), (5, 5), (5, 5), (5, 5), (5, 5), (5, 5)]
[1, 2, 3, 4], [1, 2, 3, 4, 5, 6] ->
[(1, 1), (2, 2), (3, 3), (4, 4),
(1, 5), (2, 6), (3, 1), (4, 2),
(1, 3), (2, 4), (3, 5), (4, 6)]

• can we assume a separate variable is passed to function with the length of each array or do you want us to find the length of the input strings?
– tom
Jan 10, 2020 at 17:50
• Yes, that's acceptable. Jan 10, 2020 at 18:15
• Related Jan 10, 2020 at 18:45
• Can we sort the input by array length? Jan 10, 2020 at 20:56
• @Shaggy No, I'd say you can't. Jan 11, 2020 at 6:42

# J, 14 13 bytes

,./@($&>~*./)  Try it online! -1 byte thanks to Bubbler This answer takes the two lists as its left arg, and the two list lengths as its right arg. • ($&>~*./) is a dyadic hook which applies gcd between the two right arg lengths *./ and the reshapes the two left arg lists $ to that length after opening them &>. At this point they'll be the same length so boxing is no longer needed. • [:,./ so now we can just zip them ,. ## original answer taking the lists directly ## J, 17 16 bytes (*.&#$[),.*.&#$]  Try it online! • *.&# is the gcd *. after taking length # of both args It turns out to be shorter to repeat this phrase than to remain DRY. • ,. is zip and and $ is shape. So we shape the left arg [ by the gcd of the list lengths, do the same to the right arg ], and zip them.
• 13 bytes ([: -> @). Jan 13, 2020 at 7:06
• Thanks Bubbler, don't know how I missed that :) Jan 13, 2020 at 12:59

# C (clang), 70 68 bytes

i;f(*a,*b,x,y){for(i=0;printf("(%d,%d)",a[i%x],b[i%y]),++i%x+i%y;);}


Try it online!

Takes input as pointer to a and b and the lengths, prints q to std out.

We use the modulo of an iterator by the data lengths e.g. i % x and i % y to access data, when both modules are equal to 0 , i is LCM and the function terminates.

# Jelly, 7 bytes

ṁ€æl/}Z


A dyadic Link accepting a list of the two lists on the left and a list of their respective lengths on the right which yields a lists of lists.
(A monadic Link accepting only the left argument costs 8 bytes, ṁ€Ẉæl/$Z) Try it online! Or see the test-suite. ### How? ṁ€æl/}Z - Link: list of lists [a, b], list [length(a), length(b)] } - use the right argument as the left argument of: / - reduce by: æl - least common multiple (i.e. LCM(length(a), length(b)) € - for each list in the left argument (i.e. for x in [a,b]): ṁ - mould like (i.e. repeat x cyclically until its length is the calculated LCM) Z - transpose  # R, 696054 51 bytes function(a,b,x,y)cbind(rep(a,y/sum(!(1:x*y)%%x)),b)  Try it online! Loosely based on my answer to this question. Takes a,b, and the lengths as x and y, respectively. Returns a two-column matrix. Thanks to Robin Ryder for saving 4 bytes, and then another 3. Relies on the identity $$\xy=GCD(x,y)\cdot LCM(x,y)\$$; repeats a by $$\y/GCD(x,y)\$$ times to get it to the LCM length, and cbind automatically recycles b accordingly. • 56 bytes Jan 10, 2020 at 20:31 • @RobinRyder ahhh, of course. Thanks! Jan 10, 2020 at 21:52 • 51 bytes, assuming I didn't make a mistake with operator precedence... Jan 11, 2020 at 23:34 • @RobinRyder wow, that's clever! I'm not 100% sure, but this is using the identity that x*y = gcd(x,y) * lcm(x,y), and the sum(...) is computing the gcd? Jan 13, 2020 at 14:09 • Yes, that's right! Jan 13, 2020 at 19:47 # J, 8 bytes *.&#$&>;


Try it online!

Takes two vectors as left/right args and gives a two-row matrix where each column represents a pair. If you insist a two-column matrix, prepend [:|: to the code, which is still shorter than previous J answer.

### How it works

*.&#$&>; NB. Tacit function; left=vector 1, right=vector 2 ; NB. Nested 2-item vector of two vectors$&>   NB. Disclose each and recycle to the length of...
*.&#      NB. LCM of the lengths
NB. Two disclosed vectors automatically form a 2-row matrix


# 05AB1E, 7 bytes

€g.¿δ∍ø


Takes the input as a pair of lists of integers.

Explanation:

€g       # Get the length of each inner list in the (implicit) input-pair of lists
.¿     # Take the Least Common Multiple for the two values in this pair of lengths
δ∍   # Extend both inner list in the (implicit) input-pair of lists to this length
ø  # Then zip/transpose the (now equal-length) list of lists, swapping rows/columns
# (after which the result is output implicitly)


# Perl 6, 3936 25 bytes

-3 bytes thanks to Jo King

{zip $_>>[^[lcm]($_)X%*]}


Try it online!

### Explanation

{                       }  # Anonymous block
$_>>[ ] # Index into both input arrays ^[lcm]($_)       # Range [0,lcm)
X%*    # modulo array size
zip  # Zip


# C (gcc), 85 76 bytes

n;z(a,i,j)int*a;{for(n=0;a[n*2+i+j]=a[n%i],a[n+++n+i+j]=a[n%j+i],n%i+n%j;);}


Try it online!

Thanks to ceilingcat for reduction 85->76 bytes.

The code above is golfed so that all the information is stored in a single integer array, which saves 2 bytes; the logic though is the same as previously with three arrays.

Try code with three arrays online this code has less bytes, but the arrays are global so that information is not directly passed in or out of function.

# How

description of algorithm with ungolfed code or at least less golfed code.

setup (see online code)

• a[],b[] input data - q[] output data
• i,j length of a,b
• n loop counter

do{                              }while(n%i+n%j);}
// open loop that ends when counter mod i and j =0
q[n*2]=a[n%i];
// q[0,2,4...]=a[0,1,2...]
q[n+++n]=b[n%j];
// q[1,3,5...]=b[0,1,2...]  and increase loop counter


In the golfing process all the data input and output was put into a single int array. The first i members are the contents of a, the next j members are the contents of b and the remainder of the array is filled with zeroes so that when q is calculated it can be placed directly after the b items in the same array the first zero in the array indicates q end. This use of a single integer array for data input and output saves 2 bytes. OP has indicated that this approach is acceptable for this challenge.

• @AZTECCO - ok - sorry, had it as a function before, I have reinstated that - was trying to think of any way to reduce the number of bytes
– tom
Jan 12, 2020 at 16:14
• @girobuz - ok see your point - note added about the compiler flag bytes
– tom
Jan 12, 2020 at 16:19
• @AZTECCO - ok so I tried to reduce the byte count by using global variables, but if I understand correctly the point that you are making is that in the question we need to have input and output. So I reread the question and I can see your point. I will have a look at how to implement it so that there is input and output without adding too many bytes - thanks for the helpful feedback and thanks for the tio suggestion.
– tom
Jan 13, 2020 at 1:15
• @AZTECCO edited to ensure data is passed to and from function rather than using global variables - thanks for pointing it out.
– tom
Jan 13, 2020 at 2:46
• This function isn't reusable though, since n is never reset. I also don't think taking the two parameters as a joined array is valid either, though perhaps you can ask on Meta about that
– Jo King
Jan 13, 2020 at 5:23

# Perl 6, 35 bytes

{$^a <<,<<flat$^b xx($a lcm$b)/$b}  Try it online! • 30 bytes Jan 13, 2020 at 13:25 • @nwellnhof Oh, I extrapolated that out to the exact same code as your answer, so I guess I'll leave mine as is – Jo King Jan 13, 2020 at 21:17 # Charcoal, 21 bytes ≔¹ηＷ⊙θ﹪ηＬκ≦⊕ηＩＥηＥθ§λκ  Try it online! Link is to verbose version of code. Takes input as an array of arrays and outputs as a double-spaced list of pairs. Explanation: ≔¹ηＷ⊙θ﹪ηＬκ≦⊕η  Count up from 1 until the LCM of the lengths of the arrays has been reached. (This O(n²) but even O(n) would cost 3 bytes.) ＩＥηＥθ§λκ  Map over the implicit range and cyclically index both arrays. # Wolfram Language (Mathematica), 42 bytes Thread@PadRight[#,{2,LCM@@(Length/@#)},#]&  Try it online! • 35 bytes – att Sep 18, 2020 at 6:04 # Python 3.8 (pre-release), 78 76 bytes -2 bytes thanks to Noodle9 lambda a,b:zip((x:=len(b))//(g:=math.gcd(y:=len(a),x))*a,y//g*b) import math  Try it online! # APL (Dyalog Extended), 9 bytes ,¨/∧⍥≢⍴¨⍮  Try it online! Takes two input strings as left and right arguments respectively. Being able to take lengths as separate arguments doesn't really help. ### How it works ,¨/∧⍥≢⍴¨⍮ ⍝ left: string a, right: string b ⍮ ⍝ 2-item nested array of [a, b] ⍴¨ ⍝ Reshape (by cycling elements) each of [a, b] to the length of... ∧⍥≢ ⍝ LCM of lengths of a and b ,¨/ ⍝ Reduce by "pair up element-wise"  # JavaScript (ES6), 77 68 64 58 bytes Saved 6 bytes thanks to @AZTECCO Takes input as (a, b, a_length, b_length). (a,b,n,N)=>(g=i=>[[a[i%n],b[i%N]],...++i%n+i%N?g(i):[]])  Try it online! # Brachylog, 15 bytes {l×↙X}ᵛḃ₁g,?zbᵐ  Try it online! Initially, I thought "it's funny, Brachylog has a cycling zip builtin but I don't think I'll need it", but my various attempts at j and z₂-based solutions have simply refused to terminate on test cases where the second list is longer than the first. { }ᵛ For each element of the input, l the length × multiplied by ↙X something { }ᵛ comes out to the same value. ḃ₁ Convert that value to unary, g wrap it in a list, ,? append the elements of the input, z cycling zip, bᵐ and remove the first element from each element of the result.  Note that {×↙Xℕ₁}ᵛ calculates LCM, but the ℕ₁ constraint isn't necessary in this case because z fails if any element of its input is empty (since it can't be cycled). # Perl 5, 104 bytes sub f{($A,$B,%s)=@_;map[$$A[$$_[0]],$$B[$$_[1]]],grep!$s{$$_[0],$$_[1]}++,map[$_%@$A,$_%@$B],0..@$A*@$B}


Try it online!

Slightly ungolfed:

sub f {
($A,$B,%s) = @_;                #input A and B, %s is the "seen" dictionary
map [$$A[$$_[0]], $$B[$$_[1]]], #convert indexes to values from input A and B, return that.
grep !$s{$$_[0],$$_[1]}++, #filter out index pairs seen before map [$_%@$A,$_%@$B], #make array of pairs where 1st elem is #...index of A and 2nd is index of B, #...but modulo their size respectively 0..@$A*@\$B                      #loop from 0 to size_of_A * size_of_B
}


# Ruby, 52 bytes

->x,y{a=x.size;a/=g=a.gcd b=y.size;(x*b/=g).zip y*a}


Try it online!