Supongo que cuando dice “combinaciones de elementos [matemáticos] r [/ matemáticos]”, se refiere a elementos únicos, es decir, si su matriz es ['a','b','c','c'] entonces ['c','c'] no es una combinación de 2, aunque el mismo elemento aparece dos veces en la matriz original. (Si lo desea de otra manera, se lo dejo a usted para que reduzca su problema al que he declarado). De hecho, solo voy a enumerar todos los subconjuntos de [matemáticas] \ {0,1, \ ldots, K-1 \} [/ math] de tamaño [math] r [/ math], y luego puede usarlos para indexar su matriz.
Hay dos preguntas principales en cualquier problema de enumeración: ¿las he recibido todas y las he recibido dos veces? Así que pensemos como programadores funcionales, y supongamos que he resuelto el problema para todos los valores más pequeños de [math] K [/ math] y [math] r [/ math].
Lo que haremos primero es enumerar todos los subconjuntos cuyo elemento superior es 0; entonces todos aquellos cuyo elemento superior es 1; etc.
- ¿Cuál es el algoritmo más genial (programación competitiva) que hayas encontrado?
- ¿Cuál es la solución eficiente para SPOJ CCROSSX?
- ¿Por qué son importantes las pruebas para estudiar algoritmos y estructuras de datos? ¿Estudiar esas pruebas complejas es realmente necesario?
- Cómo escribir un programa para implementar la búsqueda binaria
- ¿Cuál es la forma más eficiente de implementar la unión en varias tablas (> 5 tablas) usando SQL / ANSI SQL?
subconjuntos de iteradores (K, r):
si r == 0:
rendimiento conjunto vacío
StopIteration
elif r> K:
StopIteration
más:
para 0 <= top <K:
para s en subconjuntos (arriba, r-1):
rendimiento s + {top} \\ “+” se establece la unión
StopIteration
Ahora, ¿cómo lo hicimos? ¿Golpeamos todo? Bueno, si tenemos un subconjunto cuyo elemento más grande es [math] a <K [/ math], el conjunto de elementos más pequeños es un subconjunto de [math] \ {0,1, \ ldots, a-1 \} [/ math] de tamaño [math] r-1 [/ math], por lo que se enumerará en el bucle en la parte inferior cuando top == a . Entonces estamos bien allí.
¿Enumeramos algo dos veces? Suponga que [math] K, r [/ math] son los parámetros más pequeños en los que este algoritmo enumera un subconjunto dos veces. [1] Tal falla tiene un elemento más grande [math] a [/ math], y [math] r-1 [/ math] otros elementos. (Tenga en cuenta que [math] r> 0 [/ math] porque escribimos un caso especial para [math] r = 0 [/ math] al comienzo de la rutina). Pero esto significa que los subsets(a,r-1) llamadas de subrutina subsets(a,r-1) arrojó el mismo subconjunto de otros elementos dos veces, lo que contradice nuestra suposición de minimidad. Booyah, QED, perras!
Ahora, observe que esto en realidad está escrito en estilo imperativo, en lugar de estilo funcional. Pero fue la idea de recurrir a una versión más simple del mismo problema que podríamos asumir que está resuelto, lo que hace que todo funcione. (Por supuesto, debe identificar y escribir los casos base, pero como de costumbre, son bastante fáciles).
[1] Técnicamente, suponemos que el par [math] (K, r) [/ math] es mínimo en el pedido del producto para presenciar una falla. O podría linealizar el pedido del producto y encontrar la menor falla de esa manera.
