How to generate a matrix of 3 columns where for each column there are 3 different possibilities?

Question

The problem is as follows: In a vector I have 3 sets (A, B and C). Each set can have up to 3 distinct values(0, 1 or 2). This way I need to generate all possible combinations for this case, with formula 3³ = 27 possibilities.

Example: print -> {0,0,1} - {0,1,0} - {0,1,1} - {1,0,0} - {1,0,1} - {1,1,0} - {1,1,1} - {0,0,2} - {0,2,0} - {2,0,0} - {0,1,2} - {0,2,1} - {1,2,1} - {...} - {2,2,2}

Does anyone have any idea how to accomplish this? Do you know an algorithm that does this or anything like that? It might be in Java or C#.

Answer 1

This problem is known as permutation with repetition. I searched other sources and in Portuguese to explain the problem better, but unfortunately only found garbage (sorry the term, but I’m referring to sites that copy the poorly formatted and poorly explained content from somewhere).

As for the algorithm, this problem is usually solved more easily using a recursive algorithm. Each call must generate the combinations for one of the set positions.

For example, given the set:

int[] conjunto = {0, 0, 0};

And the position p that the current call should exchange, let’s define a routine:

permute(int[] set, int p)

Remembering that the elements of conjunto has the values 0, 1 or 2 and p refers to the position of the vector, therefore, 0 <= p <= 2.

Each time you implement recursion, you need to make clear what the criteria for recursion is. In this case, it could be something like:

• If p <= 2
  1. Exchange p+1
  2. Increase conjunto[p]
  3. Repeat steps 1 and 2 while conjunto[p] < 3
  4. Cleanse conjunto[p] (set zero for future iterations)
• If p == 3
  1. Prints conjunto and returns

I know it’s complicated, but the idea here is that the method permutar will generate the combinations for a position p and call itself recursively to generate the position p+1 and so on to the limit of conjunto. When the limit is reached, print the current content and return.

The table test would be like this:

C0 C1 C2 p
0  0  0  0    permutar(conjunto, p)
0  0  0  1      |_ permutar(conjunto, p + 1)
0  0  0  2         |_ permutar(conjunto, p + 1)
0  0  0  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  0  1  2             |_ Incrementar `conjunto[p]`
0  0  1  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  0  2  2             |_ Incrementar `conjunto[p]`
0  0  2  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  0  0  2             |_ Limpar `conjunto[p]`
0  1  0  1         |_ Incrementar `conjunto[p]`
0  1  0  2         |_ permutar(conjunto, p + 1)
0  1  0  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  1  1  2             |_ Incrementar `conjunto[p]`
0  1  1  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  1  2  2             |_ Incrementar `conjunto[p]`
0  1  2  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  1  0  2             |_ Limpar `conjunto[p]`
0  2  0  1         |_ Incrementar `conjunto[p]`
0  2  0  2         |_ permutar(conjunto, p + 1)
0  2  0  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  2  1  2             |_ Incrementar `conjunto[p]`
0  2  1  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  2  2  2             |_ Incrementar `conjunto[p]`
0  2  2  3             |_ permutar(conjunto, p + 1)
         3                 |_ imprime
0  2  0  2             |_ Limpar `conjunto[p]`
0  0  0  1         |_ Limpar `conjunto[p]`
1  0  0  0     |_ Incrementar `conjunto[p]`
...

After the last row, this table repeats twice now with the first value 1 and then with the value 2.

Note that the most external version of permutar kept the value 0 in the first position while recursive calls were changing the other positions, generating all possible repetitive permutations.

The algorithm in Java for that I get like this:

public static void permutar(int[] conjunto, int p) {
    if (p == 3) {
        System.out.printf("{%d, %d, %d}%n", conjunto[0], conjunto[1], conjunto[2]);
    } else {
        do {
            permutar(conjunto, p + 1);
            conjunto[p]++;
        } while (conjunto[p] < 3);
        conjunto[p] = 0;
    }
}

And the call so:

public static void main(String[] args) {
    int[] conjunto = {0, 0, 0};
    permutar(conjunto, 0);
}

Note that the algorithm does exactly what is described above, except that the commands may be in a slightly different order.

Although the ideal was that each developer was able to solve the above problems without looking at other’s code, unfortunately this does not work, especially for those who are starting.

If you are studying algorithms, my suggestion is to look at implementations as above and try to understand how it works. Then go back to your editor and try to reimplement as you remember it. Even having looked you will probably still miss some detail.

Over time, after exercising enough you may be able to create the solution for this and other types of problem without consultation. But it’s a utopia and it’s not even right to think that all developers can just solve these challenges themselves. This would be like telling math students that they need to derive all the formulas again instead of consulting a book.