Imagine you have a 5x5 matrix (zero indexed), where only the upper right coordinates are valid. I am unsure if this is the terminology to use, so the following coordinates should be the valid ones:
(0;1)
(0;2)
(0;3)
(0;4)
(1;2)
(1;3)
(1;4)
(2;3)
(2;4)
(3;4)
The coordinates where x<=y are invalid. In this case the matrix has 10 valid elements, and for a N sized matrix the valid elements are
Elements = (N * (N - 1)) / 2
What I wanted to know is if there is a way of generating a 2D coordinate based on a zero indexed identifier, which corresponds to one of the valid coordinates.
For example, taking into account the coordinates I mentioned above, there are 10 identifiers (0 through 9), and each of them would map to a specific coordinate: index 0 would map to (0;1), and 9 would map to (3;4). I am looking for a formula, that given a specific index and the size of the matrix, would return the corresponding index.
Is this possible? so far, the only way I could think of this was through bruteforce, trying every number combination for X and Y that make this valid:
Index = 2x + 1 + y
where Y has to be between x+1 and the size of the matrix - 1
I was hoping that someone with math knowledge than me could know of a formula that would calculate this.
I hope this makes sense and is clear enough. If not, please let me know.
Thank you in advance for your help.
Yes it is possible. The reason for this is that $\mathbb{N}^2$ is countable and so is a subset.
You could use a similar enumeration like used in those proofs, e.g.:
$$ I(x,y) = \pi(N-1 -x,y) $$ where $$ \pi(x, y) := y + \sum_{i=0}^{x+y} i = y+\frac{1}{2} (x + y) (x + y + 1) $$ is the Cantor pairing function, the enumeration used for the Cantor diagonal enumeration of $\mathbb{N}^2$.
This is a bijective function. The inverse of $\pi$ can be given like this: $$ \pi^{-1} = (\pi_1, \pi_2) $$ with $$ \pi_2(z) = z - f(q(z)) \quad \pi_1(z) = q(z) - \pi_2(z) $$ and $$ f(w) = \frac{w(w+1)}{2} \quad q(z) = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor $$
The main application is to understand that $\mathbb{N}$ has the same cardinality as $\mathbb{N}^k$.
Now the translation from $\pi$ to $I$: $$ I^{-1} = (I_1, I_2) $$ and $$ x = I_1(z) = N - 1 - \pi_1(z) \quad y = I_2(z) = \pi_2(z) $$
Example:
$N = 5$, index coordinates $x$, $y$ from $0$ to $4$ each, then $I$ would index like this:
$$ \left( \begin{matrix} * & 6 & 3 & 1 & 0 \\ * & * & 7 & 4 & 2 \\ * & * & * & 8 & 5 \\ * & * & * & * & 9 \\ * & * & * & * & * \\ \end{matrix} \right) $$
First going from $(x,y) = (3,1)$ to the enumeration index:
$I(3,1) = \pi(5 - 1 - 3, 1) = \pi(1,1) = 1 + \frac{1}{2}(1+1)(1+1+1) = 4$.
And then back from the index $4$ to $x$ and $y$: $$ y = I_2(4) = \pi_2(4) = 4 - f(q(4)) = 4 - f(2) = 4 - 3 = 1 \\ x = I_1(4) = 5 - 1 - \pi_1(4) = 4 - q(4) + \pi_2(4) = 4 - 2 + 1 = 3 $$
With a bit more tinkering regarding index transformation, one can end up with the enumeration you probably want, e.g.
$$ \left( \begin{matrix} * & 0 & 1 & 3 & 6 \\ * & * & 2 & 4 & 7 \\ * & * & * & 5 & 8 \\ * & * & * & * & 9 \\ * & * & * & * & * \\ \end{matrix} \right) $$