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

Answer 1

J, ¹⁴ 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, ¹⁷ 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.

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.

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.

Answer 9

Perl 6, 35 bytes

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

Try it online!

Answer 10

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.

Answer 11

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

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}ᵛḃ₁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).

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!