[RESOLVIDO] Gerar todas as 3.268.760 combinações da Lotofácil?

Boa tarde Pessoal,

 Pesquisei bastante aqui no fórum e ainda não consegui criar um algorítimo que geras todas as 3.268.760 combinações possíveis da Lotofacil a as grave no BD (MySQL)... o post mais próximo foi: [url]http://www.guj.com.br/java/248188-loteria-30[/url]

Gerar todas as 3.268.760 combinações da Lotofácil?

Conto com o apoio de vocês!

Amigo isso pode te ajudar:

https://www.google.com.br/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&cad=rja&ved=0CEkQFjAE&url=http%3A%2F%2Fklein.sbm.org.br%2Fwp-content%2Fuploads%2F2012%2F10%2Fnu%CC%81meros-bortolossi-rdf-projeto-klein.pdf&ei=qylcUsT5G4OSkQe8h4GIDA&usg=AFQjCNE8e6u6_WUAmcanM0vVrW8Bq2VDhw&sig2=7ZNRwcy9X9WovSeUQ7vPkA

É uma binomial C(25,15). De 25 números escolhem-se 15, sendo que a ordem não importa, e não pode haver repetição.

Um programa em C para se basear:
http://www.cs.sunysb.edu/~skiena/392/programs/binomial.c

Obrigado pessoal;

Vejam o código, consigo gerar 1 aposta sem que se repita algum dos 15 números; agora estou batalhando para para que no universo de 3.268.760 apostas, nenhuma combinação entre 15 números seja igual.

public void executa(HttpServletRequest request, HttpServletResponse response)
			throws Exception {

		// Recebe dados sobre os numeros que serão sorteados
		String[] getNumerosSorteio = request
				.getParameterValues("numerosSorteio");

		// Recebe os dados da view e grava em uma variável
		long quantidadeJogos = Long.parseLong(request.getParameter("quantidadeJogos"));

		// Cria uma lista de inteiros para receber os números para sorteio
		// int[] setNumerosSorteio = null;
		List<Integer> setNumerosSorteio = new ArrayList<Integer>();

		for (int i = 0; i < getNumerosSorteio.length; i++) {
			setNumerosSorteio.add(Integer.parseInt(getNumerosSorteio[i]));
		}

		// Cria um ArrayList de inteiros para armazenar as apostas geradas
		List<Integer> prognosticos = new ArrayList<Integer>();

		// Cria os jogos de acordo com a quantidade informada
		for (int i = 0; i < quantidadeJogos; i++) {

			// Instancia a classe Aposta para receber os dados da aposta
			Aposta aposta = new Aposta();

			// Pega idUsuario e grava para vincular com as apostas
			Usuario usuario = SessaoApp.lerUsuario(request);
			aposta.setUsuarioId(usuario.getIdUsuario());

			/*
			 * Verifica qual o concurso está ativo
			 */

			// Instancia o objeto
			ConcursoDao concursoDao = new ConcursoDao();

			// Cria uma List para receber todos concursos
			List<Concurso> concursos = concursoDao.getLista();

			// Percorre a lista
			for (Concurso concurso : concursos) {

				// Verifica qual concurso está ativo
				if (concurso.getConcursoAtivo() == true) {

					// Armazena o idGrupo que esta ativo, somente um, devido a
					// RN
					aposta.setConcursoId(concurso.getIdConcurso());
				}
			}

			// Informa o grupoId "1", ou seja, participa de aposta individual
			aposta.setGrupoId(1);

			/*
			 * Captura a data atual Foi utilizado o Calendar pois a data será
			 * trabalhada
			 */
			aposta.setDataAposta(Calendar.getInstance());

			// Marca a aposta como Ativa
			aposta.setApostaAtiva(true);

			// Instancia a classe ApostaDao para adiconar o objeto ao BD
			ApostaDao apostaDao = new ApostaDao();

			// Adiciona a aposta
			apostaDao.adicionar(aposta);

			// Lógica para gerar as combinações
			// Cria 15 objetos para a selecao (List)
			for (int j = 0; j < 15; j++) {

				// Recebe um número aleatório entre 1 e 25
				int r = (int) (1 + (Math.random() * 25));

				// Verifica se "r" está na colecao (List)
				// Se contem, gera um novo numero que não se repita
				while (prognosticos.contains(r))
					// caso positivo, gera novo número
					r = (int) (1 + (Math.random() * 25));

				prognosticos.add(r);
			}

			PrognosticoAposta prognosticoAposta = new PrognosticoAposta();
			PrognosticoApostaDao prognosticoApostaDao = new PrognosticoApostaDao();
			// Aposta aposta = new Aposta();

			// Percorre o array, insere dados no objeto e grava no BD
			for (Integer prognostico : prognosticos) {
                
				// Insere dados no objeto
				prognosticoAposta.setApostaId(aposta.getIdAposta());
				prognosticoAposta.setPrognosticoAposta(prognostico);
				
				// Antes de gravar, preciso verificar se a aposta já existe, como?
				
				// Grava no BD
				prognosticoApostaDao.adicionar(prognosticoAposta);
			}
			// Limpa a lista para receber novos números
			prognosticos.clear();
		}

		request.setAttribute("mensagem", "Aposta adicionada com sucesso!"); // mensagem
		request.setAttribute("destino", "aposta-automatica-lotofacil.jsp"); // destino																

		// Redireciona para servlet Mensagem
		request.getRequestDispatcher("Mensagem").forward(request, response);
	}

Vou fazer uma analogia do que estou pensando:

Criar uma List MAE.
Criar uma List FILHA.

A FILHA terá um combinação de 15 prognósticos (números) que não se repetem entre si.
Logo, ela vai até a MAE e verifica se existe uma outro igual à FILHA.
Se não existir, ela se grava na LIST MAE, caso contrário, ela não grava e gera um nova combinação de 15 prognósticos para verificar novamente se existe, e assim vai.
Quando a MAE receber as 3 milhões de combinações que não se repetem, ela irá gravas as combinações no Banco de Dados.

Se for isso, como faria a implementação pra comparar duas LIST?

Ah, meu BD (MySQL) está gravando assim (exemplo):

Ambos são BIGINT:

apostaId | prognosticoAposta
1 | 10
1 | 7
1 | 9
1 | 2
1 | 14
1 | 23

 2       |           18
 2       |           23
 2       |           25
 2       |            1
 2       |            5

Pessoal, se precisar de algo para esclarecer o código é so falar hein, sugestões são bem vindas! Flw

Esse é o jeito mais “bruto” de fazer, provavelmente existem soluções mais otimizadas, mas se tiver bastante memória disponível pode tentar (aliás aparentemente você trabalha para alguém que trabalha com lavagem de dinheiro então recursos computacionais não são problema né? :smiley: [size=7]brincadeira…[/size] )

O algoritmo seria o seguinte:

  • Gere todos os conjuntos possíveis de 15 números. Isso se consegue com 15 loops aninhados com i de 1 até 25 (isso mesmo, 15, daí já dá para ver que o processo é pesado)
  • Para cada um desses conjuntos faça o seguinte:
    ---- Se existem números repetidos, descarte, não é um jogo válido.
    ---- Se passou na condição anterior, então esses números podem formar uma Aposta.
    ---- Guarde a Aposta em um Set
    ---- O objeto deve atender aos seguintes critérios: Implementar os métodos equals e hashCode para que o Set possa corretamente identificar as repetidas; A igualdade não deve considerar a ordem dos números.

No final do super-loop o Set conterá todos os jogos válidos.

(A explicação ficou meio atropeladona, se tiver dúvidas é só perguntar)

[quote=gomesrod]Esse é o jeito mais “bruto” de fazer, provavelmente existem soluções mais otimizadas, mas se tiver bastante memória disponível pode tentar (aliás aparentemente você trabalha para alguém que trabalha com lavagem de dinheiro então recursos computacionais não são problema né? :smiley: [size=7]brincadeira…[/size] )

O algoritmo seria o seguinte:

  • Gere todos os conjuntos possíveis de 15 números. Isso se consegue com 15 loops aninhados com i de 1 até 25 (isso mesmo, 15, daí já dá para ver que o processo é pesado)
  • Para cada um desses conjuntos faça o seguinte:
    ---- Se existem números repetidos, descarte, não é um jogo válido.
    ---- Se passou na condição anterior, então esses números podem formar uma Aposta.
    ---- Guarde a Aposta em um Set
    ---- O objeto deve atender aos seguintes critérios: Implementar os métodos equals e hashCode para que o Set possa corretamente identificar as repetidas; A igualdade não deve considerar a ordem dos números.

No final do super-loop o Set conterá todos os jogos válidos.

(A explicação ficou meio atropeladona, se tiver dúvidas é só perguntar)
[/quote]

kkkkk… lavagem de dinheiro! Nada, e um desafio pessoal e pro meu TCC msm! kkkkkk… raxei…

gomesrod, obrigado pela sugestão, vou implementar e ver como que fica!

Valew!

Estive pensando por alguns minutos no seu projeto. Tive uma idéia.

E se você fizer um Array de 25 elementos - um para cada número - e preencher esse arrays sempre com 15 uns e 10 zeros (representando os números escolhidos e rejeitados)?

Dessa forma você já mata a questão das combinações repetidas.

Á partir daí, você faz um contador binário, forçando sempre 15 bits em 1.

Então você vai ter todas as combinações possíveis, sem repetição.

A lógica do sistema binário é relativamente fácil de implementar, e a de forçar o array a ter sempre 15 uns, também.

Acho que por ai pode ser um caminho mais eficiente e veloz.

Primeira sequência possível- combinação mais baixa: 0000000000111111111111111

Última sequência possível - combinação mais alta: 1111111111111110000000000

Assim você vai somando o número binário de 1 em 1, e armazenando a sequência caso o total de uns seja 15, e rejeitando caso não seja.

Enfim, é isso. Qualquer coisa posso explicar melhor.

Abraços e bom restinho de madrugada!

Boa tarde,

Obrigado pelo atenção e apoio de todos, felizmente consegui gerar o código também com a ajuda do meu professor! Agora preciso gravar em um tabela do tipo MEMORY, do MySQL, leiam o post no link: [url]http://www.guj.com.br/java/305416-aumentar-tamanho-tabela-mysql-do-tipo-memory[/url]

Conto com o apoio da comunidade! valew

Vejam o código, bem simprão!

public class CombinacaoLotofacilSemJDBC {
	public static void main(String[] args) {
		
			int idCombinacaoLotofacil = 0;
			for (int p1 = 1; p1 <= 11; p1++) {
				for (int p2 = p1 + 1; p2 <= 12; p2++) {
					for (int p3 = p2 + 1; p3 <= 13; p3++) {
						for (int p4 = p3 + 1; p4 <= 14; p4++) {
							for (int p5 = p4 + 1; p5 <= 15; p5++) {
								for (int p6 = p5 + 1; p6 <= 16; p6++) {
									for (int p7 = p6 + 1; p7 <= 17; p7++) {
										for (int p8 = p7 + 1; p8 <= 18; p8++) {
											for (int p9 = p8 + 1; p9 <= 19; p9++) {
												for (int p10 = p9 + 1; p10 <= 20; p10++) {
													for (int p11 = p10 + 1; p11 <= 21; p11++) {
														for (int p12 = p11 + 1; p12 <= 22; p12++) {
															for (int p13 = p12 + 1; p13 <= 23; p13++) {
																for (int p14 = p13 + 1; p14 <= 24; p14++) {
																	for (int p15 = p14 + 1; p15 <= 25; p15++) {
																		
																		idCombinacaoLotofacil++;
																		
																		String pesquisa = String.format("%02d ", p1) +
																						String.format("%02d ", p2) +
																						String.format("%02d ", p3) +
																						String.format("%02d ", p4) +
																						String.format("%02d ", p5) +
																						String.format("%02d ", p6) +
																						String.format("%02d ", p7) +
																						String.format("%02d ", p8) +
																						String.format("%02d ", p9) +
																						p10 + " " +
																						p11 + " " +
																						p12 + " " +
																						p13 + " " +
																						p14 + " " +
																						p15;
																		
																		// Para acompanhar processo																		
																		System.out.println(idCombinacaoLotofacil +
																				" > " + pesquisa);
																		
																		
									
																	}
																}
															}
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
	}
}

Senhores,
Particularmente não gosto de soluções fixas, embora o problema seja fixo(25 combinadas em grupos de 15).

Segue um algoritmo que fiz para um projeto particular que está inacabado. Gera combinações com qualquer quantidade de valores.

 Atenção no método main, para testar coloque combinações que resultem em poucos jogos tipo geraCombinacao(17, 15) e retire os comentários das linhas com print e println, desta forma verá os 136 jogos gerados.

No possibities(int n, int p) considera sempre n>p não fiz verificação dentro do método.
Caso tenha alguma melhora no código favor compartilhar.

import java.math.BigInteger;

public class Combina {

	public static int possibities(int n, int p) {
		if (n == p)
			return 1;
		BigInteger nFat = factorial(n);
		BigInteger pFat = factorial(p);
		BigInteger nMinusPFat = factorial(n - p);
		BigInteger result = nFat.divide(pFat.multiply(nMinusPFat));
		return result.intValue();
	}

	public static BigInteger factorial(final int n) {
		BigInteger result = BigInteger.valueOf(n);
		for (int i = n - 1; i > 0; i--)
			result = result.multiply(BigInteger.valueOf(i));
		return result;
	}

	public static int[][] geraCombinacao(int n, int p) {
		int c = possibities(n, p);
		int[][] m = new int[c][p];
		int[] vN = new int[p];

		for (int i = 0; i < p; i++) {
			vN[i] = i;
			m[0][i] = i;
		}

		for (int i = 1; i < c; i++)
			for (int j = p - 1; j >= 0; j--)
				if (vN[j] < (n - p + j)) {
					vN[j]++;
					for (int k = j + 1; k < p; k++) {
						vN[k] = vN[j] + k - j;
					}
					for (int l = 0; l < p; l++) {
						m[i][l] = vN[l];
					}

					break;
				}

		return m;
	}

	public static void main(String[] args) {
		int[][] m = geraCombinacao(25, 15); // coloque aqui (total de dezenas,dezenas por grupo)
		for (int i = 0; i < m.length; i++) {
			for (int j = 0; j < m[i].length; j++) {
				//System.out.print((m[i][j] + 1) + " ");
			}
			//System.out.println();
		}
		System.out.println("Total de " + m.length + " combinações");

	}

}

Bom dia Pessoal,

Estou com um problema sobre essas combinações. O java não consegue terminar os calculos das 3.268.760 listas.
Acredito que seja porque faço a verificação de lista duplicada dentre as listas geradas.Tenho um crescimento linear de verificações.

Meu código faz o seguinte: Gero uma lista randomica(TreeSet) e coloco essa lista dentro de uma Lista de Lista (Set<Set>). Preciso que os dados fiquem ordenados e sem repetição.

O código funciona corretamente para pequenas combinações, como: 10,3; 15;10; etc…

Mas para combinação 25,15 ele não consegue. Segue a parte principal do código

Set<Set> listaDeLista = new HashSet<>();

for (int i = 0; i < totalCombinacoes; i++) {

        TreeSet<Integer> listNumeros = new TreeSet<>();

        while (listNumeros.size() < limiteGrupo) {
            listNumeros.add(random.nextInt(limiteCombinacao) + 1);
        }

        if (!listaDeLista.contains(listNumeros)) {
            listaDeLista.add(listNumeros);

        } else {
            i--;
        }           

}

Variáveis

totalCombinacoes seria neste caso de 25,15 : 3.268.760
limiteCombinacao seria 25
limiteGrupo seria 15

Agradeço a tenção…