Elegir k de los primeros n números
La misión
Problema
Dados dos enteros n y k, devuelve todas las formas de elegir k números distintos entre 1 y n. El orden dentro de una elección no importa, así que escribe cada elección en orden ascendente, y devuelve las elecciones en orden lexicográfico ascendente.
Ejemplos
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Por qué: las combinaciones de 4 elementos tomados de 2 en 2 son 6
Input: n = 3, k = 3
Output: [[1, 2, 3]]
Por qué: solo hay una forma de tomarlos todos
Input: n = 2, k = 0
Output: [[]]
Por qué: caso límite: no elegir nada es exactamente una elección, la vacía
Pistas
0 / 3
Construye una elección número por número. Para mantener cada elección en orden ascendente y no producir [2, 1] después de [1, 2], agrega solo números mayores que el último que agregaste.
Llama recursivamente con un valor de inicio: elige un número x desde ese inicio en adelante, llama recursivamente con inicio x + 1, luego quita x y prueba el siguiente. Guarda una copia cuando la elección tenga k números.
Poda el bucle: si todavía necesitas m números más, empezar en x solo funciona cuando x + m - 1 <= n, así que el bucle puede detenerse en n - m + 1 en lugar de n.
- Tiempo objetivo
- O(k · C(n, k))
- Espacio objetivo
- O(k · C(n, k))
Solución
Es el árbol de decisión de subconjuntos cortado a profundidad k. Cada nivel decide el siguiente número de la elección, y pasar x + 1 como siguiente inicio garantiza que cada elección se construya en orden ascendente, así que cada conjunto de números se produce exactamente una vez y la salida queda en orden lexicográfico sin costo extra. Cuando la llamada recursiva regresa, el número se quita, lo que deja la lista compartida pick tal como la encontró el bucle. El límite superior del bucle es el paso de poda: nunca se entra en una rama que no pueda reunir suficientes números. Hay C(n, k) elecciones y copiar cada una cuesta O(k), así que el tiempo es O(k × C(n, k)) y la profundidad de recursión es k.
def choose(n, k):
out, pick = [], []
def build(start):
if len(pick) == k:
out.append(pick[:]) # record a copy, pick keeps changing
return
need = k - len(pick)
for x in range(start, n - need + 2): # leave room for the numbers still needed
pick.append(x)
build(x + 1)
pick.pop() # undo before trying the next x
build(1)
return out
print(choose(4, 2)) # -> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
print(choose(3, 3)) # -> [[1, 2, 3]]
print(choose(2, 0)) # -> [[]]¿Lo que te frena es la idea y no el código? Subconjuntos lo explica.