1

I want to create every possible coloring in a vector for a given size of the vector (amount of vertices) and given possible elements (possible colors)

as an example:

for a graph with 3 vertices and I want to color it with 3 colors, I want the following possible vectors, that are gonna be my possible colorings:

0 0 0

0 0 1

0 0 2

...

2 1 1

2 1 2

...

2 0 0

1 0 0

as you can see I want both combinations like "0 0 1" and "1 0 0".

is there any way to do this efficiently?

3marco6
  • 17
  • 4
  • How do you want to store these combinations? – Chris May 18 '22 at 00:42
  • This looks like a version of the "odometer" problem, with the only difference being that the highest number in each panel of the odometer is the number of colors. – PaulMcKenzie May 18 '22 at 00:46
  • i want to store every combination in a vector, and right after I wanted to use a function to check if the coloring is valid or not – 3marco6 May 18 '22 at 00:51
  • no triple nested loop allowed? – Giogre May 18 '22 at 00:54
  • the size of the graph isn't fixed, I want to do that for every possible graph – 3marco6 May 18 '22 at 01:12
  • If you would be satisfied with a list of valid permutations, you might be able to leverage that. Otherwise, you are generating a list of all n digit base 3 numbers. – Avi Berger May 18 '22 at 01:25
  • i have thought about this possibility, but the possible number of colors also isnt fixed, so this approach would fail for bases, where u need letters etc. – 3marco6 May 18 '22 at 01:52
  • Check out this answer: https://stackoverflow.com/a/63763630/1170207 It can be easily modified to just take a N sized vector of upper limits instead of a N sized vector of vectors of ints. – Jan Christoph Terasa May 18 '22 at 03:50
  • It is not [combination](https://en.wikipedia.org/wiki/Combination) that you want but [Cartesian Product](https://en.wikipedia.org/wiki/Cartesian_product). – Jarod42 May 18 '22 at 08:43

1 Answers1

1

This is definitely possible. Refer to the below code. It also works with all the other ASCII characters. You can modify it in order to meet your demands:

#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;
    }
}
The Coding Fox
  • 1,488
  • 1
  • 4
  • 18