Necesito escribir una función para generar el Triángulo de Pascal como una tupla usando la recursión.
eg pascal(5) ((1,), (1, 1), (1, 2, 1), (1, 3, 3, 1), (1, 4, 6, 4, 1))
Puedo generarlo como una lista con la siguiente función:
def triangle(n): if n == 0: return [] elif n == 1: return [[1]] else: new_row = [1] result = triangle(n-1) last_row = result[-1] for i in range(len(last_row)-1): new_row.append(last_row[i] + last_row[i+1]) new_row += [1] result.append(new_row) return result
Y he intentado cambiar esto a una tupla:
def pascal(n): if n==0: return () elif n==1: return ((1,),) else: new_row = (1,) result = pascal(n-1) last_row = result[-1] print(last_row) for i in range(len(last_row)-1): new_row = new_row+last_row[i]+last_row[i+1] new_row = new_row +(1,) result=result+(new_row,) return result
pero no funciona y recibo el error len(last_row)-1 type int has no len
.
No estoy seguro de cómo arreglar este código y agradecería cualquier ayuda.
Creo que el problema es el result = result + new_row
línea result = result + new_row
.
Si quieres ver por qué, al pasar el mouse por debajo …
result
es una tupla de tuplas,new_row
es una tupla de números. Si agregas una tupla de números a una tupla de tuplas, ¡terminas con una tupla de tuplas y números! Como((1,), 1)
que no es lo que quieres.result = result + (new_row,)
haciendoresult = result + (new_row,)
En su primer código, simplemente agregue esta línea antes de la return
para convertir la list of lists
en tuple of tuples
:
tuple_results = tuple(tuple(x) for x in results) return tuple_results
No entregues esto para la tarea. Tu maestro (correctamente) se dará cuenta de que lo sacaste de la red. Principalmente para fines de aprendizaje en términos de lo compacto que puede ser, es decir, cómo un progtwigdor profesional de Python podría escribir esto.
Así que aquí está, la versión corta de 8 líneas:
def pascal(n): if n <= 0: return () elif n == 1: return ((1,),) else: res = pascal(n - 1) # recursive call return (*res, (1, *[n + i for n, i in zip(res[-1], res[-1][1:])], 1)) print(pascal(5))
En este caso, la parte que faltaba en su código es el operador de propagación. Lo que hace es desempaquetar esa tupla de tuplas de la llamada recursiva a la que se dirige en la siguiente fila.
Esto es bastante denso, así que vamos a descomprimirlo un poco:
return (*res, # open paren starts new tuple, *res unpacks the recursive call (1, # starts the tuple for the current row *[ # spread the result of the list comprehension n + i for n, i in # we're going to add the items in two lists zip( # here's where we combine the two lists to add res[-1], # last row of recursive call res[-1][1:] # same but shifted 1 index ), ], # end list comprehension 1) # 1 to end the current row ) # end the total result, ie tuple of rows
Esto funciona debido a cómo zip
trata con listas de diferentes longitudes. Por ejemplo, si la última fila era (1,3,3,1)
, obtendríamos zip((1,3,3,1),(3,3,1))
que sería ((1,3), (3,3), (3,1))
. Luego summos los dígitos en los pares en la comprensión y obtenemos (4,6,4)
. Apunta a los unos y ahí está la siguiente fila.