Combinatória. Gerador de combinações.

Esta calculadora gera possíveis combinações de elementos m do conjunto de elemento com tamanho n. O número de combinações possíveis, como mostrado em Combinatória. Combinações, arranjos e permutações é

A descrição do algoritmo gerador está abaixo da calculadora

Combinatória. Gerador de combinações.



Conjunto

	Valor
		

Combinação tamanho m

Calcular

O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Download 

 Link  Salvar  Widget

Algoritmo

As combinações são geradas em ordem lexicográfica. Os algoritmos utilizam índices dos elementos do conjunto. Aqui um exemplo de como funciona:
Suponhamos que temos um conjunto de 5 elementos com índices 1 2 3 4 5 (começando do 1) e precisamos gerar toda combinação tamanho m = 3.
Primeiro, nós iniciamos a primeira combinação tamanho m - índices em ordem crescente
1 2 3
Começamos checando o último elemento (ex. i = 3). Se o valor deste for menor que n - m + i, ele é acrescido de 1.
1 2 4
Novamente, checamos o último elemento, e, uma vez que ele ainda é menor que n - m + i, ele é acrescido de 1.
1 2 5
Agora, ele tem o valor máximo permitido: n - m + i = 5 - 3 + 3 = 5, então nós movemos para o elemento prévio (i = 2).
Se seu valor for menor que n - m + i, ele é acrescido de 1, e todos os elementos seguintes tem o valor ajustado para seu vizinho prévio mais 1
1 (2+1)3 (3+1)4 = 1 3 4
Então, novamente nós começamos do último elemento i = 3
1 3 5
De volta para i = 2
1 4 5
Agora finalmente ele iguala n - m + i = 5 - 3 + 2 = 4, então podemos ir para o primeiro elemento (i = 1)
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
E então,
2 3 5
2 4 5
3 4 5 - última combinação já que todos os valores estão postos nos valores máximos possíveis de n - m + i.