¿Cuál es la fórmula para hacer un mapa entre los multiíndices y los índices?

Question

¿Cuál es la fórmula para hacer un mapa entre los multiíndices y los índices? Por multiíndice, me refiero a una variable $I\in\mathbb{N}^d$ donde $|I|=\sum\limits_{i=1}^d I_i=n$ . Aquí, $d$ denota la dimensión. Básicamente, es una tupla con $d$ -elementos que suman todos a $n$ . Busco un mapa biyectivo entre este multiíndice y otro índice $i\in\mathbb{N}$ . Básicamente, tengo una entidad indexada por un multiíndice y quiero almacenarla en un vector 1-D. Para hacerlo de forma efectiva, necesito ser capaz de mapear hacia adelante y hacia atrás entre las dos representaciones. En caso de que ayude, el número de elementos donde $I\in\mathbb{N}^d$ y $|I|=n$ es el número de elementos de la expansión multinomial o $$ \begin{pmatrix}n+(d-1)\\d-1\end{pmatrix}. $$

---

Edición 1

Para dejar las cosas claras, estoy buscando un mapeo biyectivo que se parezca a esto

$$ \begin{array}{c|c} I & i\\\hline \begin{pmatrix} 3 & 0 & 0 \end{pmatrix} & 1\\ \begin{pmatrix} 2 & 1 & 0 \end{pmatrix} & 2\\ \begin{pmatrix} 2 & 0 & 1 \end{pmatrix} & 3\\ \begin{pmatrix} 1 & 2 & 0 \end{pmatrix} & 4\\ \begin{pmatrix} 1 & 1 & 1 \end{pmatrix} & 5\\ \begin{pmatrix} 1 & 0 & 2 \end{pmatrix} & 6\\ \begin{pmatrix} 0 & 3 & 0 \end{pmatrix} & 7\\ \begin{pmatrix} 0 & 2 & 1 \end{pmatrix} & 8\\ \begin{pmatrix} 0 & 1 & 2 \end{pmatrix} & 9\\ \begin{pmatrix} 0 & 0 & 3 \end{pmatrix} & 10\\ \end{array} $$ Estoy de acuerdo en que está relacionado con un sistema numérico combinatorio y la pregunta respondida aquí pero esa pregunta consistía puramente en elementos 1 y 0 en diferentes posiciones mientras que aquí tenemos índices que pueden ser enteros generales no negativos. Gracias por la ayuda.

---

Edición 2

@joriki tenía toda la razón. Aquí está el código en MATLAB/Octave que hace la indexación. Está en un orden ligeramente diferente al que puse arriba, pero, para mí, eso no importa:

i_to_I.m

% Converts a multiindex into an index.  This assumes 
%   - One multiindex per row
%   - All multiindices have the same order (sum to the same number)
function i = I_to_i(I)
    % Determine the order of the multiindex
    m = sum(I(1,:));

    % Determine the dimension of the multiindex
    d = size(I,2);

    % Stringify the multiindex
    II = arrayfun(@(x)[ones(1,x) 0],I,'UniformOutput',0)';
    II = reshape([II{:}],m+d,size(I,1))';
    II = II(:,1:end-1);

    % Determine the cumulative sum of the stringified multiindex 
    JJ = cumsum(II')';

    % Determine the dimension of the stringified multiindex
    dd = size(II,2);

    % Determine the indices
    i = zeros(size(I,1),1);
    for j=1:size(I,1)
        i(j) = my_nchoosek(0:dd-1,JJ(j,:))*II(j,:)' + 1;
    end
end

I_to_i.m

% Converts an index to a multiindex
%
% i - index (1-based)
% d - dimension of the multiindex
% n - number of the multiindex sums to
function I = i_to_I(i,d,n)
    I = cell2mat(arrayfun(@(ii)i_to_I_driver(ii,d,n),i,'UniformOutput',0));
end

% Finds the multiindices one at a time
function I=i_to_I_driver(i,d,n)

    % Determine the dimension of the stringified multiindex
    dd = d+n-1; 

    % Convert from a one based index to a zero based
    i = i-1;

    % Allocate memory for the stringified multiindex
    II = zeros(1,dd);

    % Loop over the digits backwards
    for j=dd:-1:1

        % Essentially, determine the base of the index
        y = my_nchoosek(j-1,n);

        % If the index exceeds the base
        if i >= y
            % Reduce the amount of the index by the base
            i = i - y;

            % Add a digit in this particular place
            II(j) = 1;

            % Reduce the number of digits left to place
            n = n - 1;
        end
    end

    % To convert the stringified multiindex to a multiindex, look for the
    % position of the zeros
    I = diff([0 find([II 0]==0)])-1;
end

mi_nchoosek.m

% Vectorized version of nchoosek that returns 0 when n<k
function z=my_nchoosek(n,k)
    % Find the indices where n>=k
    I = find(n>=k);

    % Allocate memory for the result
    z=zeros(size(n));

    % Compute the combination where the function is valid
    z(I) = arrayfun(@nchoosek,n(I),k(I));
end

test01.m

% Test our indexing functions on known values
I=[ 3 0 0;
    2 1 0;
    2 0 1;
    1 2 0;
    1 1 1;
    1 0 2;
    0 3 0;
    0 2 1;
    0 1 2;
    0 0 3];
i=I_to_i(I)
II = i_to_I(i,3,3)
norm(I-II,'fro')

I=[ 2 0 0;
    1 1 0;
    1 0 1;
    0 2 0;
    0 1 1;
    0 0 2];
i=I_to_i(I)
II = i_to_I(i,3,2)
norm(I-II,'fro')

Salida

> test01
i =

    1
    2
    5
    3
    6
    8
    4
    7
    9
   10

II =

   3   0   0
   2   1   0
   2   0   1
   1   2   0
   1   1   1
   1   0   2
   0   3   0
   0   2   1
   0   1   2
   0   0   3

ans = 0
i =

   1
   2
   4
   3
   5
   6

II =

   2   0   0
   1   1   0
   1   0   1
   0   2   0
   0   1   1
   0   0   2

ans = 0

Gracias de nuevo por la ayuda.

Answer 1

Su recuento parece implicar que considera $0$ que se incluya en $\mathbb N$ .

Considere la $d$ elementos como $d$ cadenas de unos separadas por $d-1$ ceros. Cada arreglo con $n$ corresponde exactamente a uno de sus multiíndices. La indexación de estos arreglos ha sido discutida al menos una vez en este sitio; ver Forma rápida de conseguir una posición de combinación (sin repeticiones) y también Wikipedia .