What's the formula to map between multiindices and indices?

Question

What is the formula to map between multiindices and indices? By multiindex, I mean a variable $I\in\mathbb{N}^d$ where $|I|=\sum\limits_{i=1}^d I_i=n$. Here, $d$ denotes the dimension. Basically, it's a tuple with $d$-elements that all sum to $n$ . I'm looking for a bijective map between this multiindex and another index $i\in\mathbb{N}$. Basically, I have an entity that's indexed by a multiindex and I want to store it in a 1-D vector. To do so effectively, I need to be able to map back and forth between the two representations. In case it helps, the number of elements where $I\in\mathbb{N}^d$ and $|I|=n$ is the number of elements in the multinomial expansion or $$ \begin{pmatrix}n+(d-1)\\d-1\end{pmatrix}. $$

Edit 1

To make things crystal clear, I'm looking for a bijective mapping that looks something like this

$$ \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} $$ I agree that it's related to a combinatorial number system and the question answered here, but that question consisted purely of 1 and 0 elements in different positions whereas here we have indices that can be general nonnegative integers. Thanks for the help.

Edit 2

@joriki was absolutely correct. Here's code in MATLAB/Octave that does the indexing. It's in a slightly different order than what I put above, but, for me, that doesn't matter:

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

my_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')

Output

Thanks again for the help!

score 1 · Accepted Answer · edited Apr 13 '17 at 12:20

1

Your count seems to imply that you consider $0$ to be included in $\mathbb N$.

Consider the $d$ elements as $d$ strings of ones separated by $d-1$ zeros. Each arrangement with $n$ ones corresponds to exactly one of your multiindices. Indexing these arrangements has been discussed at least once on this site; see Fast way to get a position of combination (without repetitions) and also Wikipedia.

edited Apr 13 '17 at 12:20

Community

1

answered Jun 22 '16 at 07:52

joriki

238,052

Thanks for the comment and for pointing me toward combinatorial indexing schemes. That being said, I can't get your encoding to work. If we have that $n=3$ and $d=4$, certainly we can encode each of the $d$ digits as string of length $n$. However, it looks like there's more than one way to encode each digit. For example, (1,0,0) and (0,1,0) both have one digit. We could use binary, but then $n$ would need to be of the form $2^m-1$ for some $m$. Basically, I'm not sure how to make your encoding work. – wyer33 Jun 22 '16 at 23:01
@wyer33: There seems to be a misunderstanding there. The strings corresponding to the multiindices in the table in your edit would be 11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111. Each run of ones encodes one number, and the runs are separated by $d-1$ zeros. These are exactly the strings of length $n+d-1$ with $n$ ones. – joriki Jun 22 '16 at 23:05
Thanks for the clarification and you're correct. Thanks for the help! – wyer33 Jun 23 '16 at 03:47

What's the formula to map between multiindices and indices?

Edit 1

Edit 2

1 Answers1