I need help with this mathematics question.
I have made a program on the computer that flattens a 3D array into a 1D array. A 3D array needs an x, y and z but by using this formula (max x * max y * max z) + (max y * max z) + max z the array becomes 1D instead.
For example: an array of 30 x 30 x 30 can have 27930 possible locations (30 * 30 * 30 + 30 * 30 + 30)
If x=3 y=5 z=1 then (3 * 5 * 1) + (5 * 1) + 1 = 21
This speeds up processing time by removing nested loops. Seems to work fine. The array is only meant to be used as a data storage so I will always know x y z as I iterate trough each coordinate.
However. I am wondering how do I go about it backwards?
Knowing 21 how do I find out x y z? Is a polynomial solving basic arithmetic however I have been unsuccessful in solving it. One idea was using x-y-z intercepts by plugging in zeros. Another was comparing first with smallest number by subtracting it (z) then with next biggest numbers (y * z) then with the biggest one (z * y * z).
Thanks in advance for your help.
As written this is not going to work - you will have index collisions in your flattened matrix and will overwrite data.
For example $(1, 1, 7)$ would also map to the 1-D index $21$
Your formula should be (edited 15-feb-2018 for zero-based indexing):
$$ k = (x \times (\max(y)+1) \times (\max(z)+1)) + (y \times (\max(z)+1)) + z$$
And you invert it with
$$z=k\mod(\max(z)+1)$$
$$y=(k-z)/(\max(z)+1)\mod(\max(y)+1)$$
And so on --- this scheme can be extended to more than just 3D
EDIT: After user929304's comment below, I looked at this again (after 2 years) and realised I could have been clearer. I've also mixed up zero-based and one-based indexing, so here's another shot at it:
A worked example.
Assume $0\leq x\leq 5$, $0\leq y\leq 7$ and $0\leq z\leq 3$.
This means that $\max(z) = 3$ and $\max(y) = 7$.
Then $(2, 3, 1)$ should translate as follows:
$$ k = 2\times((7+1)\times(3+1)) + 3\times(3+1) + 1$$
$$ k = 64 + 12 + 1 = 77 $$
Starting with 77 and knowing $\max(z)+1 = 4$ and $\max(y)+1 = 8$ we can invert to get:
$$ z = 77 \mod 4 = 1 $$
and
$$ y = (77 - 1)/4 \mod 8 = 19 \mod 8 = 3 $$
and
$$ x = ((k - z)/(\max(z)+1) - y) / (\max(y)+1) = ((77-1)/4 - 3)/8 = (19-3)/8 = 2$$
The intuition is this - we are arranging all of the elements of the 3-D array in some systematic order so that we can count them.
Think of it like hours and minutes - the minutes add up until we get to sixty then they go back to zero and the hour counter increments. In the same way, we clock up $z$ until we get to its maximum value, then increment $y$ and set $z$ to zero again.
This means that every time we add one to the $y$ value we will have skipped ahead by $\max(z)+1$ in the linear array. And every time we add one to the $x$ value, we will have taken $y$ around the clock, which means we will have incremented $z$ by $(\max(y)+1)\times(\max(z)+1)$ and this is how far we will have jumped ahead in the linear array. The above formula encodes that.