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.

Olá, junioras!

Os métodos são estáticos, é só chamá-los estaticamente com os parâmetros correctos e pronto; nem sequer é preciso instanciar a classe.

Isto está meio abandonado - deixei de trabalhar com C# há alguns anos...

Olá,

baixei a sua library e gostaria de saber se há algum exemplo de código para uso dos métodos das classes.

Desde já agradeço,

atenciosamente,

A.G.junior

Ok, Marco! Fechei o código e agora está calculando todas as combinações que necessito. Os testes que realizei com valores C(50,25) foram satisfatórios e agora é ir em frente para validar o código. Obrigado e vamos trocando idéias.

Obrigado pelo seu comentário.

Que tipo está a usar para as variáveis? O limite máximo de Integer é de 2^31, que não chega para uma combinação desse tamanho. Considere usar Int64, cujo limite superior é bem mais alto (2^63).

Olá colega, me cadastrei hj no DreamsInCode e fiquei muito impressionado com o material disponível aqui! Tb tenho grande interesse por estudos matemáticos ligados a jogos de loteria. Tenho alguma habilidade com o Delphi, mas nada sei sobre C ou C#. Sou do Brasil e por aqui o jogo com maior aceitação é a Megasena, uma modalidade de jogo 60/6. Outra que fazem sucesso são: Duplasena 50/6 - essa com 2 sorteios por concurso, Quina 80/5, dentre outras modalidades. Como podes ver, nosso governo é muito genoroso com nosso povo, rsrsr... Ultimamente tenho me dedicado a utilizar os conceitos de Redes Neurais aplicado a jogos lotéricos, mas isso vai leva um bom tempo ainda. Sobre sua função númeroDeCombinações, gostaria de saber se é possivel cálculos para C(50,20).

Meu sistema em Delphi não aguentou o tranco e tem retornado valores errados. Por hora é isso, até breve...