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:
função factorial(n) devolve (n * factorial(n - 1)); fim de função factorial
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...