How to convert an index into N coordinates?

Question

In a 1 dimensional space:

x = i

In a 2 dimensional space (of size sx, sy):

x = i / sx
y = i % sx

In a 3 dimensional space (of size sx, sy, sz):

x = i / (sy*sz)
y = (i/sz) % sy
z = i % sz

How to deal with an N dimensional space? How can these formulas be generalized?

What about the inverse conversion?

(x1, x2, ..., xn) --> i

Note: all variables are integer.

Answer 1

Imagine you have a list of indices like this

\begin{align} 0 \le i_1 < s_1 \\ 0 \le i_2 < s_2 \\ \vdots \\ 0 \le i_N < s_N \\ \end{align}

There are basically two ways of converting a set of the form $(i_1, i_2,\cdots,i_N)$ to a number and vice versa.

ROW-MAJOR ORDERING

In this case the first index $i_1$ change fastest among the index list

\begin{eqnarray} k &=& i_1 + i_2 (s_1) + i_3 (s_1 s_2) + \cdots + i_N (s_1s_2\cdots s_{N-1}) \\ &=& i_1 + s_1(i_2 + s_2(i_3 + s_3(\cdots)))\\ &=& \sum_{n=1}^Ni_nd_n = \sum_{n=1}^N i_n\prod_{m=1}^{n-1}s_m \end{eqnarray}

COLUMN-MAJOR ORDERING

In this case is the last index $i_N$ the one changing faster

\begin{eqnarray} k &=& i_1 (s_2s_3\cdots s_N) + i_2 (s_3 \cdots s_N) + \cdots + i_N \\ &=& i_N + s_N(i_{N-1} + s_{N-1}(\cdots))\\ &=& \sum_{n=1}^Ni_nc_n = \sum_{n=1}^N i_n\prod_{m=n+1}^{N}s_m \end{eqnarray}

To convert from $k$ to the set $(i_1, i_2,\ldots)$ I will assume that the operation $x/y$ rounds to the lowest integer. These are the steps

\begin{eqnarray} i_1 &=& \frac{k}{(s_2s_3s_4 \cdots)} \\ i_2 &=& \frac{k - i_1(s_2s_3s_4\cdots)}{(s_3s_4 \cdots)} \\ i_3 &=& \frac{k - i_1(s_2s_3s_4\cdots) - i_2(s_3s_4 \cdots)}{(s_4 \cdots)}\\ &\vdots& \end{eqnarray}

which can be generalized with

$$ i_n = \frac{k - \sum_{m=1}^{n-1}i_m c_m}{c_n} \quad\mbox{with}\quad c_n = \prod_{m=n+1}^{N}s_m $$

CODE EXAMPLES

Here is an example code that goes between $k$ and $(i_1,i_2,\cdots)$ using column-major ordering (C ordering, if you are familiar with C, C++, Mathematica, ...)

# converts from (i1, i2, ...) to k
# dim = [s1, s2, ...]
def idxravelC(i, dim):

   c = 1
   for l in range(len(dim)):
       c *= dim[l]

   k = 0  
   for j in range(len(dim)):
       c /= dim[j]
       k += i[j] * c

   return k

and

# converts from k to (i1, i2, ...)
# dim = [s1, s2, ...]
def idxunravelC(k, dim):

   c = 1
   for l in range(len(dim)):
       c *= dim[l]

   i = []    
   for l in range(len(dim)):

       c /= dim[l]
       j = k / c

       k -= j * c
       i.append(j)

   return i

Of course you can use numpy.unravel_index and numpy.ravel_multi_index that are way more efficient than my solution