Gerando Combinações Usando Java

Introdução

Algum tempo atrás publiquei um post de como gerar combinações utilizando os bits de um número. Para quem não leu, pode conferir o post na íntegra aqui:

https://daemoniolabs.wordpress.com/2011/02/17/gerando-combinacoes-sem-repeticao-pela-contagem-binaria-em-c/

Nesse post irei mostrar uma possível implementação desses resultados em Java.

Classe Combinacao.java

A classe combinação tem um método construtor que aceita os elementos a serem combinados e o total de elementos de cada combinação. Se esse total por acaso for zero, então todas as combinações, de qualquer tamanho, serão geradas.

Abaixo o código:

/**
 * Class name: Combinacao.java
 *
 * Classe que especifica o esquema de combinacao
 * usando a contagem binaria.
 *
 * Autor: Daemonio (Marcos Paulo Ferreira)
 * Contato: undefinido gmail com
 * Homepage: https://daemoniolabs.wordpress.com
 *
 * Mon Jul  4 14:44:14 BRT 2011
 *
 */
package combinacao;

public class Combinacao {
    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;
    }
}

Exemplo de utilização

Aqui vai um exemplo de como usar a classe acima. O processo é simples, basta você passar os elementos como um vetor de Strings e o valor de r para o método construtor. Após isso, chame o método next() para obter de cada vez uma combinação diferente.

No código abaixo são instanciados dois objetos. O primeiro objeto é referente às combinações de 5 elementos agrupados de 3 em 3. O segundo objeto representa as combinações em que os agrupamentos tem tamanhos distintos.

package combinacao;

/**
 *
 * @author daemonio
 */
public class Main {

    public static void main(String[] args) {
        String[] str =  {"uva", "pera", "laranja", "manga", "goiaba"};
        String [] saida;

        /** Combinacoes de 5 elementos agrupados
         * de 3 em 3.
         */
        Combinacao comb1 = new Combinacao(str, 3) ;
        while (comb1.hasNext()) {
            saida = comb1.next();
            System.out.println(saida[0] + "," + saida[1] + "," + saida[2]) ;
        }

        /** Todas as combinacoes de qualquer tamanho. Nesse caso, passe
         * 0 (zero) no segundo parametro.
         */
        System.out.println("**************************") ;
        Combinacao comb2 = new Combinacao(str, 0) ;
        while ( comb2.hasNext() ) {
            saida = comb2.next() ;
            // Itera em todos os elementos da combinacao
            for ( String e : saida ) {
                System.out.print(e + ",") ;
            }
            System.out.println() ;
        }

    }
}

Conclusão

Como tive que usar combinações em um projeto que estou fazendo, achei interessante postar como implementei esses conceitos em Java.

t+

16 pensamentos sobre “Gerando Combinações Usando Java

  1. Pingback: Gerando Permutações com o Java | Daemonio Labs

  2. Olá,

    essa linha coloca o bit zero na posição indicada por entrada.length. Aconselho você dar uma lidinha no primeiro link dessa postagem, que explica melhor o algoritmo para gerar as combinações.

    Se quisermos combinar 4 elementos, então entrada.length=4. Daí colocamos o bit 1 no quarto bit, fazendo 1<<entrada.length. Por conveniência do algoritmo, preferimos o bit zero e não o 1, então fazemos a negação: ~(1 << entrada.length). Assim, this.MAX = 11111…10111 — em binário — veja que só há um bit zero no quarto bit.

    Esse valor indicará quando devemos parar de gerar as combinações, que é quando this.N & this.MAX é igual a zero (nenhum bit em comum).

    Entendeu a ideia?

    Abraços

  3. Caro Daemonio,
    Tentei executar este teu código para uma Combinacao-r de (60,6).
    Aplicando a fórmula C(60,6) = 60! / [(60 – 6)! X (6!)], ao invés de gerar 50.063.860 combinações, a sua implementação gerou 376.740 combinações.
    Por que? Há alguma explicação para isto, ou há alguma falha no código ?

    • Caro Daemonio,
      Te mandei o questionamento nesta postagem do código em C também, mas na verdade seria pro código Java, deste tópico.
      Vou tentar aplicar as modificações que você me orientou lá, mas como você postou as modificações em código C, terias como mandar as modificação em Java também, pois como nunca trabalhei com bits diretamente, não tenho conhecimento neste assunto. Ex.: o tipo “uint64_t”, qual seria em java? Se puderes me ajudar nesse sentido, ficaria muito grato.

      Abraços,
      Givaldo.

      • Ah, sim.

        Em Java o tipo long é 64 bits, então você só precisa trocar o int por long.

        private long MAX ;
        private long N ;

        Acredito que o restante fica inalterado. Por segurança, utilize um cast como na seguinte linha:

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

        Estou sem como testar esse novo código no momento, então verifique para mim se está tudo ok.

        Abraços

      • É possível também tirar a dependência dos inteiros usando o conceito de vetores. Para combinar N elementos, crie um vetor de inteiros de N+1 posições. Inicie cada posição com zero. O vetor como um todo será o seu número. Incremente esse número/vetor usando a base 2, isso é, onde é zero, troque por 1 e onde é 1 troque por zero e propague o vai um. Faça isso até que a posição N do vetor seja 1, e nessa situação, finalize o processo. Para obter a combinação individualmente, é só percorrer o vetor após o incremento e verficar as posições que contêm o bit 1. Isso deixará as coisas mais lentas porém funcionará para qualquer N. Tem-se um trade-off aqui que deve ser analisado para cada situação.

  4. Vc achou interessante posta, e eu achei que foi minha salvação no projetinho de iniciante que to começando…. só posso te agradecer por compartilhar um pouco do seu conhecimento…. gostei muito por ser um código limpo sem lógicas mirabolantes como as que me deparei antes de achar seu tópico.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s