Este post é uma reedição de um post meu no euromilhoes.com.

A forma habitual de calcular combinações, que nos ensinaram na escola, é a seguinte:

No entanto, calcular desta forma numa aplicação informática levanta desde logo dois problemas:

1. A maior parte das linguagens de programação não tem uma função para calcular factoriais, embora seja muito fácil fazer uma, simplística, é certo, de forma recursiva:

   função factorial(n)
       devolve (n * factorial(n - 1));
   fim de função factorial

2. Mesmo os mais modestos factoriais atingem rapidamente o limite dos inteiros em linguagens strongly typed (isto é, quase todas as linguagens desktop, e mesmo algumas web). Por exemplo, usando Int32, o limite é 2.147.483.647, ou 4.294.967.295 (sem sinal); o reles 13! já rebenta com qualquer um deles. OK, podíamos usar inteiros de 64 bits, afinal, quase todos os processadores actuais são de 64 bits (mas o sistema operativo também tem que ser, não se esqueçam); ficávamos com limites de 9.223.372.036.854.780.000 ou 18.446.744.073.709.600.000 (sem sinal). Pois, mas basta um 21! para ficarmos logo sem pé outra vez.

Posto isto, que fazer?

Desmontando a fórmula das combinações, poderíamos chegar a uma fórmula recursiva, e respectivo algoritmo:

função númeroDeCombinações(n, k, dif)
    se (dif = k - 1) então:
        devolve ((n - dif) / (k - dif));
    senão:
        devolve (((n - dif) / (k - dif)) * númeroDeCombinações(n, k, dif - 1));
fim de função númeroDeCombinações

Como qualquer programador sabe, as funções recursivas não são lá muito amigas da performance… Para alguns factoriais mais musculados, esta função cedo ia arrastar-se nos cálculos ou, pior ainda, superar os limites de instanciação da linguagem.

O algoritmo que vou apresentar de seguida foi publicado em 1963 (não, não é gralha, é mesmo seis-três) por M. L. Wolfson e H. V. Wright.

função númeroDeCombinações(n, k)
    seja dif = n - k;

    se (k < dif) então:
        seja dif = k;
        seja k = n - dif;

    seja combinações = k + 1;

    se (dif = 0) então:
        seja combinações = 1;
    senão: se (dif >= 2) então:
        para (i = 2; i <= dif; i = i + 1)
            seja combinações = (combinações * (k + i)) / i;
        fim de para;

    devolve combinações;
fim de função númeroDeCombinações

Reparem como ainda podemos reconhecer a fórmula explicada acima neste formato não recursivo. É maravilhosamente elegante e (ainda) é o algoritmo mais rápido de sempre para se calcular o número de combinações.

O código fonte da minha implementação em C# faz parte da classe CombTools, disponível no projecto Combinatorica, devidamente comentada, com especial atenção para as partes em que a implementação é forçosamente diferente do algoritmo em pseudo-código.