homechevron_rightEstudochevron_rightMatemática

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 Combinatorics. Combinations, arrangements and permutations é
C_{n}^m=\frac{n!}{m!(n-m)!}

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

PLANETCALC, Combinatória. Gerador de combinações.

Combinatória. Gerador de combinações.

Conjunto

arrow_upwardarrow_downwardValor
Itens por página:

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

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.

URL copiado para a área de transferência
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Combinatória. Gerador de combinações.

Comentários