homechevron_rightEstudiochevron_rightMatemática

Combinatoria. Generador de Combinaciones.

Combinatoria. Generador de Combinaciones de m desde n.

Esta calculadora genera posibles combinaciones de elementos m del conjunto de elementos con tamaño n. El número de combinaciones posibles, como se muestra en Combinatoria. Combinaciones, arreglos y permutaciones, es
C_{n}^m=\frac{n!}{m!(n-m)!}

La descripción del algoritmo generador está debajo de la calculadora

PLANETCALC, Combinatoria. Generador de combinaciones.

Combinatoria. Generador de combinaciones.

Conjunto

arrow_upwardarrow_downward
Articulos por pagina:

Algoritmo

Las combinaciones se generan en orden lexicográfico. Los algoritmos utilizan índices de los elementos del conjunto.
Así es cómo funciona en el ejemplo:
Supongamos que tenemos un conjunto de 5 elementos con índices 1 2 3 4 5 (comenzando desde 1) y necesitamos generar todas las combinaciones de tamaño m = 3.
Primero iniciamos la primera combinación de tamaño m - índices en orden ascendente
1 2 3
Comenzamos por verificar el último elemento (es decir, i = 3). Si su valor es menor que n - m + i, se incrementa en 1.
1 2 4
De nuevo, verificamos el último elemento y, dado que aún es menor que n - m + i, se incrementa en 1.
1 2 5
Ahora tiene el valor máximo permitido: n - m + i = 5 - 3 + 3 = 5, por lo que pasamos al elemento anterior (i = 2).
Si su valor es menor que n - m + i, se incrementa en 1, y todos los elementos siguientes se configuran al valor de su vecino anterior más 1
1 (2+1)3 (3+1)4 = 1 3 4
Luego comenzamos de nuevo desde el último elemento i = 3
1 3 5
Volvemos a i = 2
1 4 5
Ahora finalmente es igual a n - m + i = 5 - 3 + 2 = 4, por lo que podemos pasar al primer elemento (i = 1)
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Y entonces,
2 3 5
2 4 5
3 4 5 - última combinación, ya que todos los valores se configuran a los valores máximos posibles de n - m + i.

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Combinatoria. Generador de Combinaciones.

Comentarios