c++ - 使用离散输入变量的自然域中的多对一映射？

Question

我想找到一个映射 f:X --> N，它具有多个不同维度的离散自然变量 X，其中 f 产生一个介于 0 和所有维度的乘积之间的唯一数字。例如。假设 X = {a,b,c}，尺寸为 |a| = 2, |b| = 3, |c| = 2. f 应该产生 0 到 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

当所有维度都相等时，这很容易。假设二进制例如:

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

天真地使用不同维度的这个我们会得到重叠的值:

 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

首选计算速度快的函数，因为我打算在 C++ 中使用/实现它。感谢您的帮助!

Answer 1

好的，这里最重要的部分是数学和算法。你有可变尺寸的尺寸(从最小到最大)d₀，d₁，...，d_n。具有 x_i < d< 的元组 (x₀, x₁, ... , x_n) sub>i 将代表以下数字: x₀ + d₀ * x₁ + ... + d₀ * d₁ * ... * d_n-1 * x_n

在伪代码中，我会写:

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

要在 C++ 中实现它，我的建议是创建一个类，其中构造函数将采用维数和维本身(或者只是一个包含维的 vector<int>)，以及一个接受数组的方法或包含值的相同大小的 vector 。可选地，您可以控制没有输入值大于其维度。

一个可能的 C++ 实现可能是:

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;
    }
};