c++ - C++ 中的 n 元组列表

Question

在 C++ 中创建 n 元组列表的方法是什么？给定一个数字数组，我想生成该数组中元素的所有可能的 n 元组:

在 Mathematica 中，这是通过以下方式完成的:例如

Tuples[{0, 1, 2}, 3]

生成:

0,0,0
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2
1,0,0
...
2,2,2

在 Python 中是通过(参见 How to create N-tuples in Python?)

list(product(range(0, 2), repeat=3))

但是我不知道如何在 C++ 中执行此操作。我想要一个数组 [0,1,...,num] 并生成指定长度的 n 元组。

也许在 C++ 中可以使用 std::next_permutation 或一些嵌套的 for？

Answer 1

我假设你的数字 vector 是唯一的。

您是否注意到元组看起来很像递增的数字？我们可以利用这个事实来做到这一点。

首先，要意识到我们从中提取元组元素的集合基本上构成了我们“数字系统”中的“数字”。所以我们知道我们将有 digits^tupleSize 元组。

然后我们只需增加一个计数器并从计数器中拉出“数字”。

#include <cstddef>
#include <cstdint>
#include <vector>

// Not strictly necessary. You can find other ways to end the loop
uint32_t ipow(uint32_t base, uint32_t exp)
{
    uint32_t result = 1;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

std::vector<std::vector<uint32_t>> tuples(const std::vector<uint32_t> &set, uint32_t tupleSize)
{
    std::vector<std::vector<uint32_t>> result;

    uint32_t maxValue = ipow(set.size(), tupleSize);

    for (uint32_t counter = 0; counter < maxValue; counter++) {
        std::vector<uint32_t> tuple(tupleSize);

        uint32_t currentValue = counter;
        for (size_t i = 0; i < tupleSize; i++) {
            uint32_t digit = currentValue % set.size();
            tuple[tupleSize - i - 1] = set[digit];
            currentValue /= set.size();
        }

        result.push_back(tuple);
    }

    return result;
}

Demo