递归生成数字组合

Question

我有一个问题，正在尝试使用某种递归算法（使用 C++）来解决。

假设有两个数组：[0x10, 0x01] 和 [2, 4]。

算法应返回的结果是两个位掩码的所有组合，其中每个位掩码的非零部分可以是从 0 到第二个数组中对应值的任何值。

例如，对于上面的数组，我必须生成一个包含值的数组（或向量）：

0x00 (both bitmasks are 0)
0x01 (first bitmask is 0, second is 1)
0x02 (first bitmask is 0, second is 2)
0x03 (first bitmask is 0, second is 3)
0x10 (first bitmask is 1, second is 0)
0x11 (first bitmask is 1, second is 1)
0x12 (first bitmask is 1, second is 2)
0x13 (first bitmask is 1, second is 3).

如果该解释没有意义，请使用以下两个数组的另一个示例： [0x100, 0x010, 0x001] 和 [2, 3, 2] 将产生以下值：

0x001
0x010
0x011
0x020
0x021
0x100
0x101
0x110
0x111
0x120
0x121

我正在尝试制定一个递归算法，它接受这两个数组，并输出数组或向量中所有可能的组合，但无法完全弄清楚该算法。如有任何帮助，我们将不胜感激。

我尝试使用带有循环计数器数组的递归算法，该数组可以计算循环遍历某个位掩码索引的次数，但仍然无法完成该算法。

Answer 1

注意

GetAllResults

做了一些检查，如果您确实可以确保（

stdr

是

std::ranges

；如果您不能使用 C++20，您可以将

std::any

与迭代器对一起使用），则没有必要。我们还假设

maxTimes[i] * bitmasks[i]

不会彼此重叠（如您的示例所示）。

void GetAllResults_(const std::vector<unsigned int>& bitmasks,
    const std::vector<unsigned int>& maxTimes, unsigned int depth,
    unsigned int currVal, std::vector<unsigned int>& result)
{
    // assume: arr[i] == 0x0..1..0.
    unsigned int newDepth = depth + 1;
    if (newDepth == bitmasks.size())
    {
        for (unsigned int i = 0; i < maxTimes[depth]; i++)
            result.push_back(currVal + i * bitmasks[depth]);
        return;
    }

    for (unsigned int i = 0; i < maxTimes[depth]; i++)
    {
        unsigned int newVal = currVal + i * bitmasks[depth];
        GetAllResults_(bitmasks, maxTimes, newDepth, newVal, result);
    }
    return;
}

std::vector<unsigned int> GetAllResults(const std::vector<unsigned int>& bitmasks,
    const std::vector<unsigned int>& maxTimes)
{
    if (bitmasks.size() != maxTimes.size() || bitmasks.empty() || maxTimes.empty())
        return {};
    if (stdr::any_of(maxTimes, [](unsigned int time) { return time > 0x10; }))
        return {};

    std::vector<unsigned int> result;
    GetAllResults_(bitmasks, maxTimes, 0, 0, result);
    return result;
}

int main()
{
    auto result = GetAllResults({ 0x100,0x010, 0x001 }, { 2,3,2 });
    // output as you like
    return 0;
}