获取具有给定大小和元素的向量中的每个组合（顺序很重要）

Question

我想为给定的矢量大小（顶点数量）和给定的可能元素（可能的颜色）在矢量中创建所有可能的着色

举个例子：

对于一个有 3 个顶点的图，我想用 3 种颜色给它着色，我想要以下可能的向量，它们将是我可能的着色：

0 0 0

0 0 1

0 0 2

...

2 1 1

2 1 2

...

2 0 0

1 0 0

如您所见，我想要“0 0 1”和“1 0 0”这样的组合。

有什么有效的方法吗？

Answer 1

这绝对有可能。参考下面的代码。它还适用于所有其他 ASCII 字符。您可以修改它以满足您的需求：

#include <iostream>
#include <vector>
#include <string>

inline std::vector<std::string> GetCombinations(const char min_dig, const char max_dig, int len)
{
    std::vector<std::string> combinations;
    std::string combination(len, min_dig);

    while (true)
    {
        if (combination[len - 1] == max_dig)
        {
            combination[len - 1] = min_dig;

            int increment_index = len - 2;
            while (increment_index >= 0 && combination[increment_index] == max_dig)
            {
                combination[increment_index] = min_dig;
                increment_index--;
                if (increment_index == -1) break;
            }
            if (increment_index == -1) break;
            combination[increment_index]++;
            combinations.push_back(combination); continue;
        }
        combination[len - 1]++;
        combinations.push_back(combination);
    }

    return combinations;
}

int main()
{
    std::cout << "Enter the number of digits: "; int len; std::cin >> len;
    std::cout << std::endl;
    
    // '0' is the minimum character. '2' is the maximum character. len is the length.
    std::vector<std::string> combinations = GetCombinations('0', '2', len);

    for (auto& i : combinations)
    {
        std::cout << i << std::endl;
    }
}

获取具有给定大小和元素的向量中的每个组合（顺序很重要）

Get every combination (order is important) in vector with given size and elements

c++

combinations