Gerando Combinações Iterativamente Usando Pilhas em C

Introdução

Combinações são agrupamentos desordenados de elementos de um determinado conjunto. A necessidade de se gerar combinações de elementos é uma tarefa bastante comum em computação, especialmente quando se está trabalhando com algoritmos de força bruta em que os agrupamentos devem ser testados um por um a fim de se obter a solução ótima de um problema.

Frequentemente, esses agrupamentos são gerados de forma recursiva, embora ela seja mais fácil de implementar, ela fica limitada à pilha do sistema operacional, o que inviabiliza a geração de muitos agrupamentos.

Nessa postagem, iremos aprender como gerar as combinações de fora iterativa usando a TAD Pilha como estrutura de armazenamento. Se você deseja somente um código para combinar elementos de um vetor, pule para o fim da postagem.

Combinações-r

Dado um conjunto de N elementos, gerar as combinações-r dele é mostrar todas as sequências desordenadas de r elementos desse grupo. Isso é, para r=3, os agrupamentos de três elementos, {1, 2, 3} e {1, 3, 2}, representam o mesmo agrupamento, pois a ordem dos elementos não gera agrupamentos diferentes.

Em se tratando de combinações sem repetição, o valor de r deve ser menor ou igual a N. O total de agrupamentos é obtido pelo coeficiente binomial: N!/r!(N-r)!.

Ao se variar o r de 0 a N, isso é, gerar todas as combinações de qualquer tamanho, forma-se um outro conjunto, chamado de conjunto potência, que é definido como o conjunto de todos os subconjuntos de um conjunto. O tamanho do conjunto potência é 2^N.

TAD Pilha

Um Tipo Abstrato Pilha fornece duas operações básicas: Empilha() e Desempilha(). Dado uma lista de elementos, restringimos o acesso a ela impondo que um elemento só é acrescentando ou retirado de seu topo. A operação Empilha() serve para adicionar um elemento no topo e a Desempilha() retira esse elemento do topo, retornando-o.

Um esquema para se entender a pilha é lembrar da pilha de pratos de um restaurante: assim que pratos sujos vão chegando, eles são colocados (empilhados) um em cima do outro. O primeiro prato que será lavado (ou desempilhado) será o que está no topo da pilha.

Intuição

Primeiramente, vamos observar a intuição de como as combinações são geradas. Suponha, por exemplo, os seguintes elementos {1, 2, 3, 4, 5} e que queiramos gerar combinações de r=3 elementos. Os agrupamentos formados serão:

{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}
{2, 3, 4}, {2, 3, 5}, {2, 4, 5}
{3, 4, 5}

O total de combinações-r dado N elementos é 5!/2!3! = 10.

A primeira linha contém todos os agrupamentos que começam com 1, a segunda todos com 2 e a terceira com 3. Embora os agrupamentos sejam desordenados, podemos utilizar um padrão ordenado para termos uma ideia de como gerar todos eles.

A regra para obter os agrupamentos da linha 1 é: fixe dois elementos {1, 2}. Acrescente nesse conjunto todos os N-2=3 elementos restantes, cada um formando uma nova combinação: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}. Como não há como acrescentar mais elementos, então trocamos o segundo elemento para o 3, e adicionamos os N-3=2 elementos restantes: {1, 3, 4}, {1, 3, 5}. Não há mais elementos, então trocamos o segundo por 4, e adicionamos os N-4=1 elementos restantes, formando {1, 4, 5}. Ao se trocar o segundo elemento por 5, não temos demais elementos a adicionar, pois N-5=0. Isso acaba as combinações da primeira linha.

E para gerar as combinações da segunda linha? É o mesmo processo, porém todas elas devem começar com o com 2. Fixando os dois primeiros elementos, {2, 3}, adicionamos os N-3=2 elementos seguintes, formando {2, 3, 4}, {2, 3, 5}. Trocamos o 3 pelo 4 e adicionamos os N-4=1 elementos restantes: {2, 4, 5}. Trocamos o 4 pelo 5 e observamos que N-5=0, então mudamos de linha.

Para a terceira linha, fixamos dois elementos: {3, 4}. Adicionamos os N-4=1 elementos restantes, formando {3, 4, 5}. Trocamos o 4 pelo 5 e vemos que não há como adicionar mais elementos, dessa maneira, trocamos de linha. O primeiro elemento será o 4 e fixando dois elementos, {4, 5} adicionamos os N-5=0 elementos restantes. Porém não temos esse elemento, e assim nada é gerado e finalizamos o algoritmo.

Generalizando

Para se elaborar um conceito geral é preciso usar os benefícios da pilha. Dada uma combinação qualquer, por exemplo, {1, 2, 3}, temos que pensar nela como os elementos de uma pilha, sendo o mais à direita, o 3, o topo. Para se gerar novas combinações, o topo é desempilhado, incrementado e o resultado empilhado. Nesse caso em particular, o 3 seria desempilhado e o 4 empilhado no lugar, formando assim o novo agrupamento {1, 2, 4}. Em alguma hora será impossível variar o topo, como em {1, 2, 5}. Nessa situação, o 5 é desempilhado mas não é incrementado. A operação de desempilhar se propaga para o 2, e o 3 é empilhado no lugar. O próximo elemento ao 3 é o 4, então ele é empilhado para formar a combinação {1, 3, 4}. Por esse simples esquema, vemos que sempre que um elemento é desempilhado, seu próximo elemento é que entrará na pilha. Caso ele não possa ser variado, a operação de desempilhar é propagada até que se encontre um possível elemento de ser variado. Se isso não ocorrer, o processo se finaliza. A imagem abaixo esquematiza isso:

Figura 1: Esquema Pilha

As linhas em vermelho são combinações válidas. As verdes são empilhamentos feitos até que a pilha atinja um tamanho r ou até quando não há mais elementos a adicionar. As linhas em azul é o estado da pilha após um desempilhamento (último elemento impossível de ser variado).

Pseudocódigo

O pseudocódigo a seguir representa o que foi visto.

     1	   i=1
     2	   N = número de elementos
     3	   P = pilha inicialmente vazia
       
     4	   while(Pilha não vazia ou i < N)
     5	      para cada elemento c próximo ou igual a i
     6	         Empilha(P, c)
       
     7	         if tamanho P == r
     8	            { temos uma combinação válida quando
     9	            { o tamanho da Pilha for igual ao r passado }
    10	            combinacao = itens de P
       
    11	            { coloque aqui qualquer função que faça uso
    12	            { de uma combinação }
       
    13	            { desempilha o topo }
    14	            Desempilha(P)
       
    15	      { desempilha o anterior }
    16	      i = Desempilha(P) + 1

O laço interno (5-14) monta uma combinação de tamanho r e varia o elemento do topo até não poder mais. Quando isso acontecer, o Desempilha() da linha 16 é executado para se tentar variar elementos anteriores ao antigo topo. O processo termina quando o último elemento é alcançado (i == N) e a pilha está vazia.

Prova e Complexidade

Não entrarei em nenhuma prova formal para demonstrar que o algoritmo visto funciona para todos as entradas N. Como intuição de prova, veja que na Figura 1 são geradas não só os agrupamentos desejados como também outros agrupamentos menores. Isso é, o algoritmo gera todo o conjunto potência do conjunto de entrada e filtra somente os subconjuntos de tamanho r.

Sabe-se que a cardinalidade do conjunto potência é 2^N, indicando que a complexidade do algoritmo é O(2^N).

Código para combinar elementos de vetores em C

Os arquivos são (retire a extensão .docx)

• Comb.h
• Comb.c

eles já implementam a TAD Pilha internamente. Para testar, usaremos o seguinte exemplo:

/*
 * [exemplo.c]
 * Testa a biblioteca de gerar combinações.
 *
 * [Compilação]
 * $ gcc -o exemplo exemplo.c Comb.c
 *
 * [Uso]
 * $ ./exemplo <r> <N elementos>
 * exemplo:
 * $ ./exemplo 2 maca uva abacaxi
 *    maca        uva 
 *    maca    abacaxi 
 *     uva    abacaxi
 */

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

int main(int argc, char **argv) {
    struct comb *c ;
    int r = atoi(argv[1]) ;
    int i ;

    int *saida = malloc(r * sizeof(int)) ;

    /* 1) Passamos o tamanho total do vetor
     * de entrada.
     * 2) O vetor que receberá as permutações.
     * 3) O tamanho do r.
     */
    c = init_comb(argc-2, saida, r) ;

    /* Para obter todas as permutações chame proxCombinacao()
     * em um loop testando se o retorno é 1. Se zero, as
     * combinações foram todas geradas.
     */
       
    while(proxCombinacao(c) == 1) {
        /* Mostra a combinação */
        for(i=0; i < r; i++) printf("%10s ", argv[2+saida[i]]) ;
        putchar('\n') ;
    }

    return 0 ;
}

Compilando:

$ gcc -o exemplo exemplo.c Comb.c

Testando:

$ ./exemplo 4 maca uva pera abacaxi manga goiaba
      maca        uva       pera    abacaxi 
      maca        uva       pera      manga 
      maca        uva       pera     goiaba 
      maca        uva    abacaxi      manga 
      maca        uva    abacaxi     goiaba 
      maca        uva      manga     goiaba 
      maca       pera    abacaxi      manga 
      maca       pera    abacaxi     goiaba 
      maca       pera      manga     goiaba 
      maca    abacaxi      manga     goiaba 
       uva       pera    abacaxi      manga 
       uva       pera    abacaxi     goiaba 
       uva       pera      manga     goiaba 
       uva    abacaxi      manga     goiaba 
      pera    abacaxi      manga     goiaba 

Basicamente, é necessário uma variável do tipo struct comb e um vetor de inteiros de r posições. A variável do tipo struct comb é inicializada através da função init_comb() que recebe o total N de elementos,  o vetor de saída e o tamanho r das combinações. Para se obter combinações, basta chamar a função proxCombinacao() passando a variável comb como parâmetro. A função retorna 1 quando ainda há combinações para se gerar e zero quando tudo foi gerado. A construção mais comum é usar essa função como a condição de um loop.

Conclusão

O método visto gera combinações iterativamente usando a TAD Pilha como método de armazenamento. O algoritmo é bastante rápido para entradas pequenas, mas devido ao seu custo exponencial, o tempo de execução cresce abruptamente para ligeiros aumentos na entrada.

Referências

[1] Gerando Combinações Pela Contagem Binária by Daemonio (Acessado em: Abril/2014)
https://daemoniolabs.wordpress.com/2011/02/17/gerando-combinacoes-sem-repeticao-pela-contagem-binaria-em-c/