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:

formula_combinacoes

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:

formula_combinacoes_recursiva

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.

Partilhar no Sapo Links Partilhar no del.icio.us Partilhar no Digg Partilhar no Twitter Partilhar no StumbleUpon Partilhar no MySpace Partilhar no Facebook

Comentários Comentários Imagem do Feed RSS

Marco

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...

junioras

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

vixtrader

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.

Marco

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).

vixtrader

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...

Comentários Deixar um comentário

 Categorias
 Arquivo
 Projectos em Destaque
 Últimas Postas no Blog
 Últimos Comentários do Blog