Este problema é conhecido como permutação com repetição. Pesquisei outras fontes e em Português para explicar o problema melhor, mas infelizmente só encontrei lixo (desculpe o termo, mas estou me referindo a sites que copiam o conteúdo mal formatado e mal explicado de algum lugar).
Quanto ao algoritmo, geralmente este problema é resolvido mais facilmente usando um algoritmo recursivo. Cada chamada deve gerar as combinações para uma das posições do conjunto.
Por exemplo, dado o conjunto:
int[] conjunto = {0, 0, 0};
E a posição p
que a chamada atual deve permutar, vamos definir uma rotina:
permutar(int[] conjunto, int p)
Lembrando que os elementos do conjunto
tem os valores 0
, 1
ou 2
e p
se refere à posição do vetor, portanto, 0 <= p <= 2
.
Cada vez que você for implementar recursividade, você precisa deixar claro qual é o critério para a recursão. Neste caso, poderia ser algo como:
- Se
p <= 2
- Permutar
p+1
- Incrementar
conjunto[p]
- Repetir passos 1 e 2 enquanto
conjunto[p] < 3
- Limpar
conjunto[p]
(atribuir zero para futuras iterações)
- Se
p == 3
- Imprime
conjunto
e retorna
Eu sei que é complicado, mas a ideia aqui é que o método permutar
vai gerar as combinações para uma posição p
e chamar a si mesmo recursivamente para gerar a posição p+1
e assim por diante até o limite do conjunto
. Quando o limite for atingido, imprime o conteúdo atual e retorna.
O teste de mesa seria assim:
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]`
...
Após a última linha, essa tabela repete duas vezes agora com o primeiro valor 1
e depois com o valor 2
.
Note que a versão mais externa do permutar
manteve o valor 0
na primeira posição enquanto as chamadas recursivas foram alterando as demais posições, gerando todas as permutações com repetição possíveis.
O algoritmo em Java para isso fico assim:
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;
}
}
E a chamada assim:
public static void main(String[] args) {
int[] conjunto = {0, 0, 0};
permutar(conjunto, 0);
}
Note que o algoritmo faz exatamente o que está descrito acima, exceto que os comandos podem estar em uma ordem um pouco diferente.
Embora o ideal fosse que cada desenvolvedor fosse capaz de resolver os problemas acima sem olhar código alheio, infelizmente isso não funciona, principalmente para quem está começando.
Se você está estudando algoritmos, minha sugestão é olhar implementações como acima e tentar entender como ela funciona. Depois, volte para seu editor e tente reimplementar como você lembra dela. Mesmo tendo olhado você ainda provavelmente vai perder algum detalhe.
Com o tempo, após exercitar bastante você pode ser capaz de criar a solução para este e outros tipos de problema sem consulta. Mas é uma utopia e nem é correto achar que todos os desenvolvedores podem simplesmente resolver esses desafios por si mesmos. Isso seria como dizer para os alunos de matemática que eles precisam derivar todas as fórmulas novamente ao invés de consultar um livro.