Resolução de problemas/Combination

Combinação

Na análise combinatória, a combinação C(n, k) (lê-se: n elementos tomados k a k vezes) define um subconjunto de n com k elementos. O número de combinações é o coeficiente binomial:

Problemas que envolvem a formação de subconjuntos à partir de um determinado espaço amostral podem ser resolvidos usando-se combinação. Por exemplo:

Dado grupo de 100 pessoas, deseja-se formar comissões de 20 pessoas cada. Quantas comissões diferentes podem ser formadas?

R: C(100,20)

Numa escolinha de basquete 30 alunos estão inscritos. Sabendo-se que uma equipe de basquete é composta por 5 atletas, quantas equipes diferentes podemos formar (independente das posições)?

R: C(30, 5)

Perceba que nos problemas de combinação a ordem dos elementos dentro de um subconjunto não importa.

Para calcularmos computacionalmente o valor exato de n elementos tomados k a k vezes usando a fórmula binomial acima pode tornar-se impossível quando trabalhamos com valores de n e k muito grandes, visto que estamos trabalhando com fatoriais. Tome por exemplo o valor exato de 100!:

100! = 93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,

       468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,

       697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

Um valor que certamente não caberá em um long long int do C. Mesmo que o valor final da combinação caiba em uma variável do tipo long long int, perceba que no denominador da fração há uma multiplicação de fatoriais! Assim, os valores intermediários podem ultrapassar a faixa de valores desse tipo de dados, causando um overflow. Vale salientar que na resolução desse problema a utilização de tipos ponto-flutuante não é permitida.

Então, como fazemos para calcularmos combinações com valores de n e k muito grandes? Por exemplo, C(100, 10)?

Uma possível solução é usarmos o Triângulo de Pascal: um triângulo numérico infinito formados por binômios , em que n representa o número da linha e k o número da coluna.

Calculando o valor dos binômios, temos o seguinte triângulo:

Agora, se quisermos calcular C(100,10) basta calcularmos o elemento que está na 100ª linha e 10ª coluna. Todavia, não é necessário calcularmos o valor de todos os binômios, apenas precisamos conhecer a Relação de Stiffel: cada número do Triângulo de Pascal é igual à soma do número imediatamente acima e seu antecessor.

= +

Abaixo segue uma possível implementação em C para o cálculo de combinações à partir do Triângulo de Pascal:

 int main(){
 	long long int p[MAX+1][MAX+1], N, K;
 	int i, j;
 	for(i = 0; i < MAX+1; i++){
 		for(j = 0; j <= i; j++){
 			if(j == 0 || j == i) p[i][j] = 1;
 			else p[i][j] = p[i-1][j] + p[i-1][j-1];
 		}
 	}
 	while(1){
 		scanf("%lld %lld",&N, &K);
 		if(N == 0 && K == 0) break;
 		printf("%lld things taken %lld at a time is %lld exactly.\n", N, K, p[N][K]);
 
 	}
 	return 0;
 }

No primeiro trecho do programa, preenchemos o Triângulo de Pascal conforme a Relação de Stiffel. Observe que a 1ª coluna e a diagonal principal devem ser sempre preenchidas com 1.

Em seguida, apenas imprimos na tela a combinação de N tomados K a K vezes.

Veja esse problema em: http://acm.uva.es/p/v3/369.html