DreamsInCode logo

DreamsInCode

import { Research, Work, Passion } from Life;

Imagem de Algoritmo para Loto-Aplicações – Número de CombinaçõesImagem de Algoritmo para Loto-Aplicações – Número de Combinações

Dylan Nolte @ Unsplash

Algoritmo para Loto-Aplicações – Número de Combinações

Algoritmos para calcular o número de combinações.

Publicado Tuesday, January 19, 2010 at 12:35 AM

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

Ckn=n!k!×(nk)C_k^n = \frac{n!}{k! \times (n - k)}

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:
1função factorial(n)
2 devolve (n * factorial(n - 1));
3fim de função factorial
  1. Mesmo os mais modestos factoriais atingem rapidamente o limite dos tipos inteiros. Por exemplo, usando Int32, o limite é 2.147.483.647, ou 4.294.967.295 (sem sinal); o reles 13!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!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:

Ckn=[(n0)/(k0)]×[(n1)/(k1)]××([n(k1)]/[k(k1)])\begin{aligned} C_k^n = [(n - 0) / (k - 0)] \newline \times [(n - 1) / (k - 1)] \newline \times \dots \newline \times ([n - (k - 1)] / [k - (k - 1)]) \end{aligned}
1função numeroDeCombinacoes(n, k, dif)
2 se (dif = k - 1) então:
3 devolve ((n - dif) / (k - dif));
4 senão:
5 devolve (((n - dif) / (k - dif)) * numeroDeCombinacoes(n, k, dif - 1));
6fim de função numeroDeCombinacoes

As funções recursivas, porém, não são lá muito amigas da performance… mesmo com tail optimization (que este exemplo nem tem). Para alguns factoriais mais musculados, esta função cedo ia arrastar-se nos cálculos.

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.

1função numeroDeCombinacoes(n, k)
2 seja dif = n - k;
3
4 se (k < dif) então:
5 seja dif = k;
6 seja k = n - dif;
7
8 seja combinações = k + 1;
9
10 se (dif = 0) então:
11 seja combinações = 1;
12 senão: se (dif >= 2) então:
13 para (i = 2; i <= dif; i = i + 1)
14 seja combinações = (combinações * (k + i)) / i;
15 fim de para;
16
17 devolve combinações;
18fim de função numeroDeCombinacoes

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

Lotarias
Algoritmos

Postas relacionadas