1

O problema é o seguinte: Em um vetor eu tenho 3 conjuntos (A, B e C). Cada conjunto pode ter até 3 valores distintos(0, 1 ou 2). Dessa forma eu preciso gerar todas as combinações possíveis para esse caso, com fórmula 3³ = 27 possibilidades.

Exemplo: 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}

Alguém tem alguma ideia de como realizar isso? Conhece algum algoritmo que faça isso ou algo parecido? Pode ser em Java ou C#.

2
  • 1
    Bem vindo ao sopt. Primeiro decida uma linguagem, citar varias sem relação atrapalha um pouco a resposta.
    – user28595
    1/03/2016 às 0:44
  • 2
    Bom, creio que uma grande gama de usuários poderiam responder a sua questão com um mínimo esforço possível. Inclusive eu mesmo poderia, porém, creio que essa questão possua um intuito bem didático, portanto, acredito fortemente que seria uma boa oportunidade de você iniciar no mundo do desenvolvimento, caso queira seguir essa área. 1/03/2016 às 1:36

1 Resposta 1

2

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
    1. Permutar p+1
    2. Incrementar conjunto[p]
    3. Repetir passos 1 e 2 enquanto conjunto[p] < 3
    4. Limpar conjunto[p] (atribuir zero para futuras iterações)
  • Se p == 3
    1. 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.

2
  • 1
    Obrigado, me ajudou bastante. Na verdade a minha tarefa é um pouco mais complexa do que essa, eu usei esse exemplo apenas para ter uma base por onde seguir, já que eu conheço pouco de algoritmo. No problema real os conjuntos não possuem números inteiros, mas sim objetos/instâncias de classes e associações de um modelo UML. Você poderia me indicar um livro que fale sobre algoritmos recursivos?
    – Marcos
    1/03/2016 às 17:58
  • @Marcos infelizmente não tenho em mente nenhum material sobre o assunto, nem sei se existe um. Geralmente você precisa primeiro identificar o tipo do problema e então fica fácil encontrar um algoritmo para resolver, sendo que muitos têm a versão recursiva e a iterativa.
    – utluiz
    1/03/2016 às 22:18

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .