Gerando Combinações Sem Repetição Pela Contagem Binária Em C

Introdução

Em um post anterior eu falei sobre como gerar as permutações-r com repetição. Nesse post pretendo ensinar como gerar combinações sem repetição dos elementos de um grupo de entrada. A linguagem utilizada aqui será a C, mas os conceitos vistos aqui podem ser facilmente portados para qualquer outra linguagem.

Definições

Combinação: é o agrupamento de algum ou todos elementos de um conjunto com elementos distintos. A combinação dos elementos [1,2,3] gera os seguintes agrupamentos: [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]. Repare que a ordem dos elementos em cada agrupamento não é importante, logo mudar a ordem dos elementos não gera combinações diferentes.

Combinações-r: são todos os agrupamentos de tamanho r resultantes da combinação do grupo de entrada. No exemplo acima, a combinação-2 do grupo [1, 2, 3] forma os agrupamentos: [1, 2], [1, 3].

A quantidade de agrupamentos resultantes de uma combinação-r é:

n!/(n-r)!*r!

onde n é a quantidade de elementos e r é o tamanho de cada agrupamento.

A quantidade total, variando-se o r de 0 a n, é de:

Cn, 0 = n!/(n-0)!*0!
+
Cn, 1 = n!/(n-1)!*1!
+
Cn, 2 = n!/(n-2)!*2!
+
Cn, 3 = n!/(n-3)!*3!
+
...
+
Cn, r=n = n!/(n-n)!*n!
=
2^n

Exemplo:

para n= 5
C5, 0 = 1
+
C5, 1 = 5
+
C5, 2 = 10
+
C5, 3 = 10
+
C5, 4 = 5
+
C5, 5 = 1
=
Total: 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5

O método

O método para gerar todas as combinações de um conjunto consiste em casar as posições dos bits 1 de um número natural com as posições dos elementos do conjunto dado. Após esse mapeamento de posições, uma combinação será gerada. Como cada número natural gera um sequência binária diferente de todos os outros números, então cada agrupamento será único, o que está de acordo com a definição da combinação (a ordem dos elementos não gera um novo agrupamento).

Considere o número 3 em binário, 101. Se pensarmos que cada bit 1 ativa uma posição em específico, então as posições 0 (a primeira da direita para esquerda) e 2 foram selecionadas. Se varrermos todos os números entre 00000(2) e 11111(2), estaremos gerando todas as combinações para os n=5 elementos de entrada. Cada vez que o número é incrementado, os bits 1’s variam de posição, gerando assim agrupamentos diferentes. Daí para se gerar combinações de qualquer conjunto, simplesmente usamos as posições ativadas pelo bit 1 para selecionar elementos desse conjunto.

Exemplo

Considere a string: “abcd”. A tarefa aqui será gerar todas as combinações desses caracteres. Repare que o r aqui é variável, não estamos interessados no tamanho dos agrupamentos, e sim, como gerar todos eles. Como a string tem tamanho n=4, precisaremos varrer todos os números entre 0000(2) e 1111(2).

A tabela abaixo exemplifica o método utilizado. A primeira coluna representa todos os números no intervalo [0000(2), 1111(2)]. Já a segunda coluna contém os caracteres da string “abcd” que foram ativados pelos bits 1’s do número da primeira coluna.

+-------------------+-----------------+
|Número em binário  |  Combinação     |
+-------------------+-----------------+
|       0000        |     ""          |
+-------------------+-----------------+
|       0001        |     {a}         |
+-------------------+-----------------+
|       0010        |     {b}         |
+-------------------+-----------------+
|       0011        |   {a, b}        |
+-------------------+-----------------+
|       0100        |     {c}         |
+-------------------+-----------------+
|       0101        |   {a, c}        |
+-------------------+-----------------+
|       0110        |   {b, c}        |
+-------------------+-----------------+
|       0111        |  {a, b, c}      |
+-------------------+-----------------+
|       1000        |     {d}         |
+-------------------+-----------------+
|       1001        |   {a, d}        |
+-------------------+-----------------+
|       1010        |   {b, d}        |
+-------------------+-----------------+
|       1011        |  {a, b, d}      |
+-------------------+-----------------+
|       1100        |   {c, d}        |
+-------------------+-----------------+
|       1101        |  {a, c, d}      |
+-------------------+-----------------+
|       1110        |  {b, c, d}      |
+-------------------+-----------------+
|       1111        |  {a, b, c, d}   |
+-------------------+-----------------+

Repare que o mapeamento acontece da direita para a esquerda. Os bits menos significativos mapeiam os elementos iniciais da entrada. (ex: 0001 ativa o {a} e não o {d})

Código para gerar todas as combinações

Abaixo um código que gera todas as combinações dos caracteres de uma string de entrada.

/*
 * [comb.c]
 * Programa que gera todas as combinações dos caracteres
 * de uma string de entrada.
 *
 * [Autor]
 * Marcos Paulo Ferreir (Daemonio)
 * undefinido gmail com
 * https://daemoniolabs.wordpress.com/
 *
 * [Uso]
 * $ gcc -o comb comb.c
 * $ echo 'abcd' | ./comb
 *
 * Versão 1.0 by daemonio @ Thu Feb 17 08:17:31 BRST 2011
 *
 */
#include <stdio.h>
#include <string.h>

/* Tamanho máximo da entrada */
#define MAX_INPUT 31

int main() {
    unsigned MAX, MASK, NUM ;
    int i, j ;
    /* Armazena a string de entrada. */
    char input[MAX_INPUT] ;
    /* Armazena cada combinação. */
    char str[MAX_INPUT] ;

    printf("Digite o grupo inicial: ") ;
    scanf("%s", input) ;

    /* Manda o bit 1 para a n-ésima posição.
     * Os bits são invertidos para que a posição n
     * esteja com o bit zero, a fim de marcar
     * o final do processo.
     */
    MAX = ~(1 << strlen(input)) ;

    /* Primeiro número é o 1. */
    NUM = 1;

    putchar('\n') ;

    /* Quando o número alcançar MAX, o loop
     * será encerrado.
     */
    while ( MAX & NUM ) {
        MASK = 1 ;
        i = j = 0 ;

        while ( MAX & MASK ) {
            /* Verdadeiro se NUM tem um bit 1
             * na posição indicada por MASK. */
            if ( NUM & MASK ) {
                /* Gera a combinação em str. */
                str[i] = input[j] ;
                i++ ;
            }
            j++ ;
            /* Desloca a máscara */
            MASK = MASK << 1 ;
        }

        str[i]=0 ;
        printf("%s\n", str) ;

        NUM++ ;
    }

    return 0;
}

Exemplo de execução

Primeiro compilamos o programa:

$ gcc -o comb comb.c

em seguida um exemplo de execução:

$ ./comb
Digite o grupo inicial: 12345
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
5
15
25
125
35
135
235
1235
45
145
245
1245
345
1345
2345
12345

Explicação do código

1)

#define MAX_INPUT 31
...
...
    MAX = ~(1 << strlen(input)) ;

    NUM = 1;
    putchar('\n') ;

    while ( MAX & NUM ) {

Essa operação AND diz quando o processo todo chegou ao fim. Como sabemos, a quantidade final de combinações é de 2^n, sendo n a quantidade de elementos. Uma maneira mais fácil de calcular 2^n, sem usar funções como pow(), é deslocando o bit 1 para a posição n de um número inteiro. Após o deslocamento, invertemos os bits por comodidade, pois é mais fácil entender que, quando NUM estiver com o bit da posição n ligado, o processo deve ser terminado. O problema disso é que o tamanho da entrada é prejudicado, sendo que ela deve ter no máximo 31 caracteres (considerando uma máquina 32 bits). Se você precisa que a entrada seja maior que 31 (o 32o bit será usado para o teste), tente um long long int ou simplesmente implemente o problema de outra maneira (ex: usando big nums).

2)

        MASK = 1 ;
        i = j = 0 ;

        while ( MAX & MASK ) {
            if ( NUM & MASK ) {
                str[i] = input[j] ;
                i++ ;
            }
            j++ ;
            MASK = MASK << 1 ;
        }

Como verificar quais bits estão ativados em determinado número? A única maneira possível é iterando, e é isso que o while faz. A variável MASK se inicia com valor 1, e a cada iteração, esse bit 1 vai sendo deslocado para uma posição à esquerda. Em seguida, na condição do loop, um AND é feito com as variáveis MAX e MASK para testar se o processo chegou ao fim. Repare que o loop termina quando o único bit ativo de MASK alcançar a posição do único bit vazio de MAX.

O if testa se o bit correspondente de MASK está ativo em NUM. Se sim, então devemos gerar uma combinação, utilizando as variáveis i e j como índices dos vetores str (resultado) e input (string de entrada).

3)

        str[i]=0 ;
        printf("%s\n", str) ;

Mostra o resultado na tela.

Gerando combinações-r

O código anterior gera todo tipo de agrupamento, mesmo aquelas com diferente quantidade elementos. Nessa parte iremos ver como gerar as combinações-r de um conjunto. A diferença agora é que um r será dado para indicar a quantidade de elementos de cada agrupamento.

Não tem mistério algum. O valor de r nos diz a quantidade exata de bits 1 que se deve ter no número NUM. O que vai mudar em relação ao código anterior é que agora teremos um loop para contar quantos bits 1 estão ativados no número. De posse dessa quantidade, iremos comparar essa quantidade com o r dado, e se forem iguais, uma combinação-r será gerada.

/*
 * [combr.c]
 * Programa que gera combinações de tamanho r de
 * todos caracteres de uma string de entrada.
 *
 * [Autor]
 * Marcos Paulo Ferreira (Daemonio)
 * undefinido gmail com
 *
 * [Uso]
 * $ gcc -o combr combr.c
 * $ ./combr
 *   abcd <-- digite a string
 *   3    <-- digite o r
 *
 * Versão 1.0 by daemonio @ Thu Feb 17 08:17:31 BRST 2011
 *
 */

#include <stdio.h>
#include <string.h>

/* Tamanho máximo da entrada */
#define MAX_INPUT 31

int main() {
    unsigned MAX, MASK, NUM ;
    int i, j, r, k ;
    /* Armazena a string de entrada. */
    char input[MAX_INPUT] ;
    /* Armazena cada combinação. */
    char str[MAX_INPUT] ;

    printf("Digite o grupo inicial: ") ;
    scanf("%s", input) ;

    printf("Digite o r: ") ;
    scanf("%d", &r) ;

    /* Manda o bit 1 para a n-ésima posição.
     * Os bits são invertidos para que a posição n
     * esteja com o bit zero, a fim de marcar
     * o final do processo.
     */
    MAX = ~(1 << strlen(input)) ;

    /* Primeiro número é o 1. */
    NUM = 1;

    putchar('\n') ;

    /* Quando o número alcançar MAX, o loop
     * será encerrado.
     */
    while ( MAX & NUM ) {
        /* Conta os bits 1's. */
        MASK = 1 ;
        k = 0 ;
        while ( MAX & MASK ) {
            if ( NUM & MASK ) k++ ;
            MASK = MASK << 1 ;
        }

        /* Monta o resultado somente se
         * a quantidade de bits k é igual
         * a r. */
        if ( k == r ) {
            MASK = 1 ;
            i = j = 0 ;

            while ( MAX & MASK ) {
                /* Verdadeiro se NUM tem um bit 1
                 * na posição indicada por MASK. */
                if ( NUM & MASK ) {
                    /* Gera a combinação em str */
                    str[i] = input[j] ;
                    i++ ;
                }
                j++ ;
                /* Desloca a máscara */
                MASK = MASK << 1 ;
            }

            str[i]=0 ;
            printf("%s\n", str) ;
        }

        NUM++ ;
    }

    return 0;
}

Exemplo de execução

$ gcc -o combr combr.c
$ ./combr
Digite o grupo inicial: 12345
Digite o r: 3
123
124
134
234
125
135
235
145
245
345

Explicação do código

1)

    while ( MAX & NUM ) {
        MASK = 1 ;
        k = 0 ;
        while ( MAX & MASK ) {
            if ( NUM & MASK ) k++ ;
            MASK = MASK << 1 ;
        }

        if ( k == r ) {

A única parte diferente é essa. Conta-se quantos bits estão ativos no número e armazena essa quantidade em k. Em seguida, compare-se k com r, e se forem iguais, gera-se um novo agrupamento.

Conclusão

Mais um método simples para resolver problemas aparentemente complicados. O único problema aqui é a limitação da entrada que depende da quantidade de bits do inteiro da máquina. Acredito que isso não seja um grande problema para a maioria, porque o máximo de 31 bits para a entrada é possível gerar muitas combinações (para ser exato: 2.147.483.648).

Referências

[1] All Combinations Without Repetitions by phoxis (Acessado em: Julho/2012)
http://phoxis.org/2009/10/13/allcombgen

[2] Licença dos códigos postados, a pedido do phoxis (Acessado em: Julho/2012)
http://phoxis.org/about/#license