How to index multi-indices efficiently

Question

Let

$$ \Sigma_d^n = \left\{u \in \{\mathbb N \cup 0\}^n; \sum_{i = 1}^{n} u_i \leq d\right\} $$ Is there a way to index the elements of $\Sigma^n_d$, i.e. a bijective function $$F: \Sigma^n_d \rightarrow \{0, 1, \dots, |\Sigma^n_d| - 1\},$$ such that $F$ (and, if possible, $F^{-1}$) can be calculated easily, in $\mathcal O(1)$ time with respect to $d$.

---

Having thought about this a bit more, the best I found so far is this. For $u = (u_1, u_2, \dots, u_n)$, with $n \geq 1$, let

• $r(u) := (u_1, u_2, \dots, u_{n-1})$;

• $s(u) := u_1 + u_2 + \dots + u_n$;

• $s_i(u) := s(r^i(u)) = u_1 + u_2 + \dots + u_{n - i}$.

We can define by recursion the following function, independent of $d$:

$$ F^n(u) = \begin{cases} |\Sigma^n_{s(u)-1}| + F^{n-1} (r(u)) \quad &\text{if} \, n, u \neq 0 \\ 0 \quad &\text{otherwise} \end{cases} $$

Then

$$F^n(u) = \sum_{i=0}^{n-1} |\Sigma^{n-i}_{s_i(u) - 1}| = \sum_{i=0}^{n-1} \binom{n - i + s_i(u) - 1}{n-i} = \sum_{i=1}^{n} \binom{i + s_{n-i}(u) - 1}{i}$$

For completeness, here is the python code I wrote to test the formula:

from scipy.special import binom

u = [0, 0, 0, 0, 0]
n = 1000
i = 0

def increment(u):
    for i in range(len(u) - 1):
        if u[i + 1] != 0:
            u[i + 1] -= 1
            break
    else:
        i = len(u) - 1

    u[i] = 1 + u[0]

    if i != 0:
        u[0] = 0


def index(u):
    sum, result = 0, 0
    for i in range(len(u)):
        sum += u[i]
        if sum > 0:
            result += int(binom(i + sum, i + 1))
    return result


while i < n:
    print(str(index(u)) + ": " + str(u))
    increment(u)
    i += 1

Answer 1

I think one obvious idea is to establish a total order on $|\Sigma_d^n|$:

$$(u_1,u_2,\dots,u_n) > (v_1,v_2,\dots,v_n) \\\iff (\exists i \in\{1,2,\dots,n\},\, u_i>v_i)\, \text{ and }\, (\forall j\,\text{ with $1\leqslant j < i$},\, u_i = v_i)$$

Then $F$ is simply the unique order isomorphism. One can build $F$ from the ground up:

\begin{align} (0,0,\dots,0,0)&\mapsto 0\\ (0,0,\dots,0,1)&\mapsto 1\\ \vdots\\ (0,0,\dots,0,d)&\mapsto d\\ (0,0,\dots,1,0)&\mapsto d+1\\ (0,0,\dots,1,1)&\mapsto d+2\\ \vdots\\ (0,0,\dots,1,d-1)&\mapsto 2d\\ (0,0,\dots,2,0)&\mapsto 2d+1\\ \vdots\\ (0,0,\dots,2,d-2)&\mapsto 3d-1\\ (0,0,\dots,3,0)&\mapsto 3d\\ \vdots\\ (0,0,\dots,d,0)&\mapsto \frac{d(d+3)}2\\ \vdots \end{align}

There is probably some smart way to provide some formula, at least piecewise, for $F$. Might address this later.