0
$\begingroup$

An array of combinations is generated from two arrays,

               indices:  0   1   2   3   4   5
               array 1: [a,  b]      
               array 2: [A,  B,  C]
     repeating array 1:  a,  b,  a,  b,  a,  b      
     repeating array 2:   A,  B,  C,  A,  B,  C      
          combinations: [aA, bB, aC, bA, aB, bC]    length = LCM(2, 3)

INPUT : a, C
OUTPUT: 2, which the index of aC in the generated combinations.

Say, when a and C are given whose indices are already known as 0 and 2 in the original arrays, how to find the index of aC, which is 2? Is there any algorithmic way to do this?

For detailed background information, please check version 1 of this question.

$\endgroup$
0
2
$\begingroup$

(BTW, I think the code in the first edition of the question was the issue -- not the background info with respect to the sexagenary cycle, which is actually good to include to understand the motivation for the problem).

To put the problem a bit differently, you have the sets $\mathbb{Z}/m\mathbb{Z}$ = $\{0,1,...,m-1\}$ and $\mathbb{Z}/n\mathbb{Z} = \{0,1,...,n-1\}$, and you start with the pair (0,0), then (1,1), etc., basically applying the mapping $(x,y)\mapsto(x+1 \mod m,y+1 \mod n)$, until you wrap back around to $(0,0)$. In the easy case where $m=n$ then, you can see that $(i,i)$ was the $i$-th term in the sequence (0-based). In general, if you are asking about the index of $(i,j)$, then you are effectively trying to solve the system of congruences \begin{align*} x &\equiv i \mod m \\ x &\equiv j \mod n \end{align*} for $x$. Here $x$ represents how many times you did the $(+1,+1)$ operation starting with $(0,0)$.

When $m$ and $n$ are coprime, the Chinese remainder theorem gives you an algorithm to compute the solution. When they are not coprime, then that system in general may not have a solution, but in the case where the system was created by the above construction, it does. This math.stackexchange answer shows you how to find the (unique) solution in the range $[0,LCM(m,n))$.

$\endgroup$
-1
$\begingroup$

Yes, there is. Because everything is given, you only want to solve a specific instance of a more general problem. The solution is:

return 2;
$\endgroup$
1
  • $\begingroup$ Could downvoters please explain, why they think, that this answer is more unuseful than the question does not show research effort, even though 1. it exactly answers the original question. 2. the question would not even have an answer, if it was asked in a more general way. $\endgroup$ – catalyst Dec 22 '20 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.