# How can I get index of combination from element indices

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.

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))$$.
return 2;