Cartesian LCM of two arrays

Question

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 code-golf, 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)]

• tom: 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?
• Esolanging Fruit: Yes, that's acceptable.
• Giuseppe: Related
• Shaggy: Can we sort the input by array length?
• Esolanging Fruit: @Shaggy No, I'd say you can't.

Answer 1

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.

• Bubbler: 13 bytes ([: -> @).
• Jonah: Thanks Bubbler, don't know how I missed that :)

Answer 2

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.

Answer 3

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

Answer 4

R, (削除) 69 (削除ここまで) (削除) 60 (削除ここまで) (削除) 54 (削除ここまで) 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.

• Robin Ryder: 56 bytes
• Giuseppe: @RobinRyder ahhh, of course. Thanks!
• Robin Ryder: 51 bytes, assuming I didn't make a mistake with operator precedence...
• Giuseppe: @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?
• Robin Ryder: Yes, that's right!

Answer 5

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

Answer 6

05AB1E, 7 bytes

€g.¿δ∍ø

Takes the input as a pair of lists of integers.

Try it online or verify all test cases.

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)

Answer 7

Perl 6, (削除) 39 (削除ここまで) (削除) 36 (削除ここまで) 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

Answer 8

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.

• tom: @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: @girobuz - ok see your point - note added about the compiler flag bytes
• tom: @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: @AZTECCO edited to ensure data is passed to and from function rather than using global variables - thanks for pointing it out.
• Jo King: 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

Answer 9

Perl 6, 35 bytes

{$^a <<,<<flat $^b xx($a lcm$b)/$b}

Try it online!

• nwellnhof: 30 bytes
• Jo King: @nwellnhof Oh, I extrapolated that out to the exact same code as your answer, so I guess I'll leave mine as is

Answer 10

Charcoal, 21 bytes

≔1ηW⊙θ%ηLκ≦⊕ηIEηEθ§λκ

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:

≔1ηW⊙θ%ηLκ≦⊕η

Count up from 1 until the LCM of the lengths of the arrays has been reached. (This O(n2) but even O(n) would cost 3 bytes.)

IEηEθ§λκ

Map over the implicit range and cyclically index both arrays.

Answer 11

Wolfram Language (Mathematica), 42 bytes

Thread@PadRight[#,{2,LCM@@(Length/@#)},#]&

Try it online!

• att: 35 bytes

Answer 12

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!

Answer 13

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"

Answer 14

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!

Answer 15

Brachylog, 15 bytes

{l×ばつ↙X}vḃ1g,?zbm

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 z2-based solutions have simply refused to terminate on test cases where the second list is longer than the first.

{ }v For each element of the input,
 l the length
 ×ばつ multiplied by
 ↙X something
{ }v comes out to the same value.
 ḃ1 Convert that value to unary,
 g wrap it in a list,
 ,? append the elements of the input,
 z cycling zip,
 bm and remove the first element from each element of the result.

Note that ×ばつ↙XN1}v calculates LCM, but the N1 constraint isn't necessary in this case because z fails if any element of its input is empty (since it can't be cycled).

Answer 16

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
}

Answer 17

Ruby, 52 bytes

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

Try it online!