Gerar Combinacoes Usando Recursao daemoniolabs.wordpress.com

/*
 * daemoniolabs.wordpress.com
 *
 * Programa que gera combinacoes usando
 * recursao.
 *
 * Pilha de execucao:
 *  comb("", abc)             -> a
 *  |--> comb(a, bc)          -> ab
 *       |--> comb(ab, c)     -> abc
 *           |--> comb(abc, ) -> <nada>
 *       |--> comb(ab,  )     -> <nada>
 *       |--> comb(a,  c)     -> ac
 *            |--> comb(ac, ) -> <nada>
 *  |--> comb("", bc)         -> b
 *       |--> comb(b, c)      -> bc
 *            |--> comb(bc, ) -> <nada>
 *  |--> comb("", c)          -> c
 *       |--> comb(c, )       -> <nada>
 *  |--> comb("", "")         -> <nada> (fim da recursao)
 *
 *  Para entender melhor o algoritmo aconselho anotar
 *  em um papel cada ocorrencia de recursao. Comece
 *  com combinacoes de "ab", depois de "abc", etc.
 *
 * Qui Set 29 17:12:27 BRT 2011
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void comb(char *prefix1, char *s) {
    /* devemos ter um prefix para cada funcao.
     * Nao podemos usar o parametro porque em C
     * a passagem eh feita por referencia (em
     * java eh por valor) */
    char *prefix = (char *)malloc(strlen(prefix1) + 2);

    /* s.length() > 0 */
    if ( strlen(s) > 0 ) {
        int len ;

        /* prefix = prefix do parametro. Isso
         * eh necessario pois cada funcao
         * deve ter seu prefix. */
        strcpy(prefix, prefix1) ;

        /* prefix + s.charAt(0) */
        len = strlen(prefix) ;
        prefix[len] = s[0] ;
        prefix[len+1] = '\0' ;

        /* system.out.println(prefix + s.charAt(0)) */
        printf("%s\n", prefix) ;

        /* comb(prefix + s.charAt(0) , s.substring(1)) */
        comb(prefix, s + 1) ;

        /* comb(prefix, s.substring(1)) */
        prefix[len]=0;
        comb(prefix, s + 1) ;

        free(prefix) ;
    }
}

/* funciona igual a comb(), a diferenca
 * eh que o tamanho da combinacao final
 * eh testado com r, se forem iguais,
 * mostra na tela. */
void comb2(char *prefix1, char *s, int r) {
    char *prefix = (char *)malloc(strlen(prefix1) + 2);

    if ( strlen(s) > 0 ) {
        int len ;

        strcpy(prefix, prefix1) ;

        len = strlen(prefix) ;
        prefix[len] = s[0] ;
        prefix[len+1] = '\0' ;

        if ( strlen(prefix) == r ) {
            printf("%s\n", prefix) ;
        }

        comb2(prefix, s + 1, r) ;

        prefix[len]=0;
        comb2(prefix, s + 1, r) ;

        free(prefix) ;
    }
}

int main() {

    /* use para gerar combinacoes de
     * qualquer tamanho. O primeiro parametro
     * deve ser sempre "" e o segundo eh a
     * sequencia de entrada. */
    puts("** Todas as combinacoes de abc **") ;
    comb("", "abc") ;

    /* use para gerar combinacoes
     * com r elementos. */
    puts ("** Combinacoes de tamanho 4 **") ;
    comb2("", "123456789", 4) ; /* combinacoes de 4 elementos */

    return 0;
}