Lógica para gerar combinações nas Loterias

5 respostas
adrianoaquino

Boa noite Pessoal,

Estou criando um sistema que gera combinações das loterias e encontrei o seguinte código e gostaria da ajuda de vocês para entender ou até mesmo utilizar outros meios, lembrando que meu objetivo e criar todas combinações possíveis em uma modalidade.

Dúvida maior (o que é “<<”):

i = i << 1 ;

Código completo:

private int r ;
    private String[] entrada ;
    private int MAX ;
    private int N ;
 
    /** se r e' zero entao iremos fazer todas
     * as combinacoes (com qualquer quantidade
     * de elementos).
     */
    public Combinacao(String[] entrada, int r) {
        this.r = r ;
        this.entrada = entrada ;
        this.MAX = ~(1 << entrada.length) ;
        this.N = 1;
    }
 
    /** Retorna true quando ha pelo menos
     * uma combinacao disponivel.
     */
    public boolean hasNext() {
        if ( r != 0 ) {
            while ( ((this.N & this.MAX) != 0) && (countbits() != r) ) N+=1 ;
        }
 
        return (this.N & this.MAX) != 0;
    }
 
    /** Retorna a quantidade de bits ativos (= 1)
     * de N.
     */
    private int countbits() {
        int i;
        int c;
 
        i = 1;
        c = 0;
        while ( (this.MAX & i) != 0 ) {
            if ( (this.N & i) != 0) {
                c++;
            }
            i = i << 1 ;
        }
 
        return c ;
    }
 
    /** Util para obter o tamanho da saida. Esse
     * tamanho e' o numero de posicoes do vetor
     * retornado por next.
     */
    public int getSaidaLength() {
        if (r != 0) {
            return r;
        }
 
        return this.countbits();
    }
 
    /** Retorna uma combinacao.
     *
     * ATENCAO: Sempre use next() quando se
     * tem certeza que ha uma combinacao
     * disponivel. Ou seja, sempre use next()
     * quando hasNext() retornar true.
     */
    public String[] next() {
        int saida_index, entrada_index, i;
 
        String[] saida = new String[this.getSaidaLength()];
 
        entrada_index = 0;
        saida_index = 0;
        i = 1;
 
        while ((this.MAX & i) != 0) {
            if ((this.N & i) != 0) {
                saida[saida_index] = entrada[entrada_index];
                saida_index += 1;
            }
            entrada_index += 1;
            i = i << 1;
        }
 
        N += 1;
 
        return saida;

Fonte: http://daemoniolabs.wordpress.com/2011/07/04/gerando-combinacoes-usando-java/

5 Respostas

Luiz_Augusto_Prado

O operador unário de bit shifting, ou deslocamento bit-a-bit, equivale à multiplicação ou divisão por 2

6 = 0000 0110 ; deslocando 4 casas para a esquerda (6 << 4) = 0110 0000 deslocando 1 casa para a direita (6 >> 1) = 0000 0011 deslocando 2 casa para a direita (6 >> 2) = 00000 001
fonte:http://apssouza.com.br/blog/operacao-bit-a-bi/

adrianoaquino

Obrigado Luiz, muito boa sua contribuição!

Achei um complemento interessante sobre o assunto: http://arduino.cc/en/Reference/Bitshift

A respeito da linha com o “~”, achei em: http://www.guj.com.br/java/146431-operador-til-resolvido

this.MAX = ~(1 << entrada.length);

Pessoal, ainda estou tentando esclarecer mais ainda o código!

flw!

regis_hideki

Não li o código a fundo, mas acho que a ideia principal do código é a seguinte:

imagine que você tem n números (os números da cartela da loteria, por exemplo) e quer todas as combinações de p elementos (os números que serão apostados).

Então, cria-se um array binário de n posições onde cada posição representa um número. O número 1 em uma posição significa que a posição faz parte dessa combinação. Nesse caso, todo array retornado deve vir com p 1’s.

Um exemplo de todas combinações para n=4 e p=2:

0011
0101
1001
0110
1100

Um array que não tenha dois 1’s é inválido. Ex: 1110, 0111, 1111, 0000.

regis_hideki

Apaguei este post, pois foi duplicado.

adrianoaquino

[size=18][color=red]COMPLEMENTO[/color][/size]
http://www.guj.com.br/java/305238-gerar-todas-as-3…68760-combinacoes-da-lotofacil

Criado 11 de outubro de 2013
Ultima resposta 15 de out. de 2013
Respostas 5
Participantes 3