Una fila del triángulo de Pascal
La misión
Problema
Una biblioteca de probabilidad necesita todos los coeficientes binomiales desde C(k, 0) hasta C(k, k) para un k dado, que forman la fila k del triángulo de Pascal contando desde la fila 0. Dado k entre 0 y 1000, devuelve esa fila como una lista de enteros. Constrúyela en O(k) pasos aritméticos sin construir las filas de arriba.
Ejemplos
Input: k = 3
Output: [1, 3, 3, 1]
Input: k = 5
Output: [1, 5, 10, 10, 5, 1]
Input: k = 0
Output: [1]
Por qué: caso límite: la fila 0 contiene un solo 1
Pistas
0 / 3
La entrada j de la fila k es C(k, j), el número de formas de elegir j elementos entre k.
Pasar de C(k, j) a C(k, j + 1) cambia la fórmula k! / (j! (k - j)!) en un factor arriba y uno abajo.
C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Multiplica primero y luego divide con //, y la división siempre es exacta.
- Tiempo objetivo
- O(k)
- Espacio objetivo
- O(k)
Restricciones
- 0 ≤ k ≤ 1000
Solución
Cada entrada de la fila k es un coeficiente binomial, y los coeficientes vecinos difieren en una razón simple: C(k, j + 1) = C(k, j) × (k - j) / (j + 1). Partiendo de C(k, 0) = 1, cada entrada siguiente cuesta una multiplicación y una división. Multiplicar antes de dividir mantiene la aritmética exacta, porque C(k, j) × (k - j) es igual a C(k, j + 1) × (j + 1) y, por lo tanto, siempre es múltiplo de j + 1, y los enteros grandes de Python hacen que ni siquiera el centro de la fila 1000 se desborde. Esto evita construir las k filas de arriba, lo que costaría O(k²) sumas. La fila requiere O(k) pasos aritméticos y O(k) de espacio para la salida.
def pascal_row(k):
row = [1]
for j in range(k):
row.append(row[-1] * (k - j) // (j + 1)) # exact: C(k, j+1) * (j+1)
return row
print(pascal_row(3)) # -> [1, 3, 3, 1]
print(pascal_row(5)) # -> [1, 5, 10, 10, 5, 1]
print(pascal_row(0)) # -> [1]¿Lo que te frena es la idea y no el código? Permutaciones vs. combinaciones lo explica.