Help para um novato - Combinações de números (RESOLVIDO

9 de julho de 2020 6 respostas

LuizCunha 9 de julho de 2020

Olá pessoal, estou estudando Java e gostaria da ajuda de vocês. Dado que tenho um vetor com 12 números, e desejo gerar n conjuntos de 6 elementos com esses números. Calculando tenho 924 possíveis combinações sem repetições. Preciso de sugestões de como proceder para gerar todas esses 924 conjuntos de 6 números sem repetir números em cada conjunto e também não repetir um mesmo conjunto. Muito Obrigado, agradeço por qualquer ajuda.

package Estudos;

public class Combinacao {

public static void main(String[] args) 	{
	
int[] numeros  =  {4,5,13,17,24,33,49,50,51,52,53,54};
	
	int numCombinacoes;
	int fatorialTotalElementos = 1;
	int fatorialConjuntoDesejado = 1;
	
	//calcula o Fatorial de 12 elementos
	for (int i = 1; i<= numeros.length;i++) {
		fatorialTotalElementos =+ fatorialTotalElementos*i;
	}

	//Calcula o Fatorial de 6 elementos
	for (int i = 1;i<=6;i++) {
		fatorialConjuntoDesejado =+ fatorialConjuntoDesejado*i;
	}
	//Calcula o número de combinações possíveis	sem repetições
	numCombinacoes= (int) (fatorialTotalElementos/(Math.pow(fatorialConjuntoDesejado,2)));
    System.out.println(numCombinacoes);	
      }
  
     
  	   }

6 Respostas

Jelson1 9 de jul. de 2020

Essa parece ser difícil! Eu não sei como fazer isso, mas pesquisando por algoritmos de enumeração cheguei nesses links:

https://www.ime.usp.br/~pf/algoritmos/aulas/enum.html

https://pt.slideshare.net/mobile/datar/19-algoritmos-de-enumeracao

Apesar de não ter encontrado o algoritmo em Java, isso pode ser um ponto de partida. Talvez outra pessoa do fórum possa ajudar. De qualquer forma vou ficar acompanhando esse tópico. Fiquei curioso para saber a solução!

Edit: Encontrei esse algoritmo, relativamente fácil de implementar:

import java.util.*;

class Main {
  public static void main(String[] args) {
    //Entrada
    int n = 12;
    int r = 6;
    
    List<int[]> combinations = generate(n, r);
    for (int[] combination : combinations) {
      System.out.println(Arrays.toString(combination));                                                          
    }
    System.out.printf("generated %d combinations of %d items from %d ", combinations.size(),n, r);
  }
  
  private static void helper(List<int[]> combinations, int data[], int start, int end, int index) {
    if (index == data.length) {
        int[] combination = data.clone();
        combinations.add(combination);
    } else if (start <= end) {
        data[index] = start;
        helper(combinations, data, start + 1, end, index + 1);
        helper(combinations, data, start + 1, end, index);
    }
  }
  
  private static List<int[]> generate(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    helper(combinations, new int[r], 0, n-1, 0);
    return combinations;
  }
}

Fonte: https://www.baeldung.com/java-combinations-algorithm

LuizCunha 9 de jul. de 2020

Legal, muito obrigado, vou estudar esse código, acho que dá pra adaptar.

Jelson1 9 de jul. de 2020

Eu fiz mais uma adaptação, adicionando um paramentro que é um array de int (elementos) na qual você que gerar as combinações:

import java.util.*;

class Main {
  public static void main(String[] args) {
    //Entrada
    int[] numeros = {4,5,6,8,10,12};
    int n = 6;
    int r = 3;

    List<int[]> combinations = generate(n, r, numeros);
    for (int[] combination : combinations) {
      System.out.println(Arrays.toString(combination)); 
    }
    System.out.printf("generated %d combinations of %d items from %d ", combinations.size(),n, r);                     
}

  private static void helper(List<int[]> combinations, int data[], int start, int end, int index, int[] elementos) {
    if (index == data.length) {
    int[] combination = data.clone();
      combinations.add(combination);
    } else if (start <= end) {
      data[index] = elementos[start];
      helper(combinations, data, start + 1, end, index + 1, elementos);
      helper(combinations, data, start + 1, end, index,elementos);
    }
  }

  private static List<int[]> generate(int n, int r, int[] elementos) {
    List<int[]> combinations = new ArrayList<>();
    helper(combinations, new int[r], 0, n-1, 0,elementos);
    return combinations;
  }
}

E troquei essa linha da função helper:

data[index] = start;

Por essa:

data[index] = elementos[start];

Isso deu certo porque a variável start pode ser vista como os índices de uma lista, então você pode adaptar para qualquer tipo de objetos!

LuizCunha 9 de jul. de 2020

Jelson,

Cara, esse código resolveu tudo, fiz uma pequena alteração incluindo o vetor com os números que eu precisava, alterei os nomes das variáveis e métodos para o português, apenas pra ficar didático pra mim. Mas simplesmente usei 100% o código que você me passou, muito obrigado, segue abaixo o código.
package Estudos;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Main {

public static void main(String[] args) {

// Entrada.

int n = 12;

int r = 6;

List<int[]> combinacoes = gerado(n, r);

for (int[] combinacao : combinacoes) {

System.out.println(Arrays.toString(combinacao));

}

System.out.println();

System.out.printf("Foram Geradas %d combinações de %d elementos em conjuntos de %d elementos, sem repetições  ",

combinacoes.size(), n, r);

}

private static void Ajudante(List<int[]> combinacoes, int dados[], int inicio, int fim, int indice) {
	int[] numeros = new int[] { 4, 5, 13, 17, 24, 33, 49, 50, 51, 52, 53, 54 };

	if (indice == dados.length) {
		int[] combinacao = dados.clone();
		combinacoes.add(combinacao);
	} else if (inicio <= fim) {
		dados[indice] = numeros[inicio];
		Ajudante(combinacoes, dados, inicio + 1, fim, indice + 1);
		Ajudante(combinacoes, dados, inicio + 1, fim, indice);
	}
}

private static List<int[]> gerado(int n, int r) {
	List<int[]> combinacoes = new ArrayList<>();
	Ajudante(combinacoes, new int[r], 0, n - 1, 0);
	return combinacoes;
}

}

LuizCunha 9 de jul. de 2020 1 like

Então, penamos da mesma forma, usei a variável start como posição do array que eu já tinha. Show de bola, só preciso entender melhor a lógica, rss.

Jelson1 9 de jul. de 2020

Esse foi o site onde encontrei o algoritmo , tá em inglês, mas vale apena dá uma olhada. É bem interessante, apesar de que eu não entendi muito bem!

Criado 9 de julho de 2020

Ultima resposta 9 de jul. de 2020

Respostas 6

Participantes 2

6 Respostas

Topicos relacionados