A many-to-one mapping in the natural domain using discrete input variables?

Question

I would like to find a mapping f:X --> N, with multiple discrete natural variables X of varying dimension, where f produces a unique number between 0 to the multiplication of all dimensions. For example. Assume X = {a,b,c}, with dimensions |a| = 2, |b| = 3, |c| = 2. f should produce 0 to 12 (2*3*2).

a b c | f(X)
0 0 0 | 0
0 0 1 | 1
0 1 0 | 2
0 1 1 | 3
0 2 0 | 4
0 2 1 | 5
1 0 0 | 6
1 0 1 | 7
1 1 0 | 8
1 1 1 | 9
1 2 0 | 10
1 2 1 | 11

This is easy when all dimensions are equal. Assume binary for example:

f(a=1,b=0,c=1) = 1*2^2 + 0*2^1 + 1*2^0 = 5

Using this naively with varying dimensions we would get overlapping values:

 f(a=0,b=1,c=1) = 0*2^2 + 1*3^1 + 1*2^2 = 4
 f(a=1,b=0,c=0) = 1*2^2 + 0*3^1 + 0*2^2 = 4

A computationally fast function is preferred as I intend to use/implement it in C++. Any help is appreciated!

Answer 1

Ok, the most important part here is math and algorythmics. You have variable dimensions of size (from least order to most one) d₀, d₁, ... ,d_n. A tuple (x₀, x₁, ... , x_n) with x_i < d_i will represent the following number: x₀ + d₀ * x₁ + ... + d₀ * d₁ * ... * d_n-1 * x_n

In pseudo-code, I would write:

result = 0
loop for i=n to 0 step -1
  result = result * d[i] + x[i]

To implement it in C++, my advice would be to create a class where the constructor would take the number of dimensions and the dimensions itself (or simply a vector<int> containing the dimensions), and a method that would accept an array or a vector of same size containing the values. Optionaly, you could control that no input value is greater than its dimension.

A possible C++ implementation could be:

class F {
    vector<int> dims;

public:
    F(vector<int> d) : dims(d) {}

    int to_int(vector<int> x) {
        if (x.size() != dims.size()) {
            throw std::invalid_argument("Wrong size");
        }
        int result = 0;
        for (int i = dims.size() - 1; i >= 0; i--) {
            if (x[i] >= dims[i]) {
                throw std::invalid_argument("Value >= dimension");
            }
            result = result * dims[i] + x[i];
        }
        return result;
    }
};