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+