Combinatória. Gerador de combinações.
Combinatória. Gerador de combinações de m a n.
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
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.
Comentários