Triángulo de Pascal para Python

Como experiencia de aprendizaje para Python, estoy tratando de codificar mi propia versión del triángulo de Pascal. Me tomó algunas horas (ya que estoy empezando), pero salí con este código:

pascals_triangle = [] def blank_list_gen(x): while len(pascals_triangle) < x: pascals_triangle.append([0]) def pascals_tri_gen(rows): blank_list_gen(rows) for element in range(rows): count = 1 while count < rows - element: pascals_triangle[count + element].append(0) count += 1 for row in pascals_triangle: row.insert(0, 1) row.append(1) pascals_triangle.insert(0, [1, 1]) pascals_triangle.insert(0, [1]) pascals_tri_gen(6) for row in pascals_triangle: print(row) 

que devuelve

 [1] [1, 1] [1, 0, 1] [1, 0, 0, 1] [1, 0, 0, 0, 1] [1, 0, 0, 0, 0, 1] [1, 0, 0, 0, 0, 0, 1] [1, 0, 0, 0, 0, 0, 0, 1] 

Sin embargo, no tengo idea de a dónde ir desde aquí. Me he estado golpeando la cabeza contra la pared durante horas. Quiero enfatizar que NO quiero que lo hagas por mí; solo empujame en la direccion correcta Como lista, mi código vuelve.

 [[1], [1, 1], [1, 0, 1], [1, 0, 0, 1], [1, 0, 0, 0, 1], [1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1]] 

Gracias.

EDITAR: Tomé un buen consejo y reescribí mi código por completo, pero ahora tengo otro problema. Aquí está mi código.

     import math pascals_tri_formula = [] def combination(n, r): return int((math.factorial(n)) / ((math.factorial(r)) * math.factorial(n - r))) def for_test(x, y): for y in range(x): return combination(x, y) def pascals_triangle(rows): count = 0 while count <= rows: for element in range(count + 1): [pascals_tri_formula.append(combination(count, element))] count += 1 pascals_triangle(3) print(pascals_tri_formula) 

    Sin embargo, estoy encontrando que la salida es un poco indeseable:

     [1, 1, 1, 1, 2, 1, 1, 3, 3, 1] 

    ¿Cómo puedo arreglar esto?

    OK revisión de código:

     import math # pascals_tri_formula = [] # don't collect in a global variable. def combination(n, r): # correct calculation of combinations, n choose k return int((math.factorial(n)) / ((math.factorial(r)) * math.factorial(n - r))) def for_test(x, y): # don't see where this is being used... for y in range(x): return combination(x, y) def pascals_triangle(rows): result = [] # need something to collect our results in # count = 0 # avoidable! better to use a for loop, # while count <= rows: # can avoid initializing and incrementing for count in range(rows): # start at 0, up to but not including rows number. # this is really where you went wrong: row = [] # need a row element to collect the row in for element in range(count + 1): # putting this in a list doesn't do anything. # [pascals_tri_formula.append(combination(count, element))] row.append(combination(count, element)) result.append(row) # count += 1 # avoidable return result # now we can print a result: for row in pascals_triangle(3): print(row) 

    huellas dactilares:

     [1] [1, 1] [1, 2, 1] 

    Explicación del triángulo de Pascal:

    Esta es la fórmula para "n elegir k" (es decir, de cuántas formas diferentes (sin tener en cuenta el orden), de una lista ordenada de n artículos, podemos elegir k artículos):

     from math import factorial def combination(n, k): """n choose k, returns int""" return int((factorial(n)) / ((factorial(k)) * factorial(n - k))) 

    Un comentarista preguntó si esto está relacionado con itertools.combination - de hecho lo es. "n elige k" se puede calcular tomando la longitud de una lista de elementos de las combinaciones:

     from itertools import combinations def pascals_triangle_cell(n, k): """n choose k, returns int""" result = len(list(combinations(range(n), k))) # our result is equal to that returned by the other combination calculation: assert result == combination(n, k) return result 

    Veamos esto demostrado:

     from pprint import pprint ptc = pascals_triangle_cell >>> pprint([[ptc(0, 0),], [ptc(1, 0), ptc(1, 1)], [ptc(2, 0), ptc(2, 1), ptc(2, 2)], [ptc(3, 0), ptc(3, 1), ptc(3, 2), ptc(3, 3)], [ptc(4, 0), ptc(4, 1), ptc(4, 2), ptc(4, 3), ptc(4, 4)]], width = 20) [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]] 

    Podemos evitar repetirnos con una lista de comprensión anidada:

     def pascals_triangle(rows): return [[ptc(row, k) for k in range(row + 1)] for row in range(rows)] >>> pprint(pascals_triangle(15)) [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1], [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1], [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1], [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1], [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1]] 

    Definido recursivamente:

    Podemos definir esto recursivamente (una definición menos eficiente, pero quizás más matemáticamente elegante) utilizando las relaciones ilustradas por el triángulo:

      def choose(n, k): # note no dependencies on any of the prior code if k in (0, n): return 1 return choose(n-1, k-1) + choose(n-1, k) 

    Y por diversión, puede ver que cada fila tarda más en ejecutarse, porque cada fila tiene que volver a calcular casi cada elemento de la fila anterior dos veces cada vez:

     for row in range(40): for k in range(row + 1): # flush is a Python 3 only argument, you can leave it out, # but it lets us see each element print as it finishes calculating print(choose(row, k), end=' ', flush=True) print() 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 ... 

    Ctrl-C para dejar de fumar cuando te cansas de verlo, se vuelve muy lento muy rápido ...

    Sé que quiere implementarse, pero la mejor manera de explicarlo es a través de una implementación. Así es como lo haría, y esta implementación se basa en mi conocimiento bastante completo de cómo funcionan las funciones de Python, por lo que probablemente no querrá usar este código por sí mismo, pero puede hacer que apunte en la dirección correcta.

     def pascals_triangle(n_rows): results = [] # a container to collect the rows for _ in range(n_rows): row = [1] # a starter 1 in the row if results: # then we're in the second row or beyond last_row = results[-1] # reference the previous row # this is the complicated part, it relies on the fact that zip # stops at the shortest iterable, so for the second row, we have # nothing in this list comprension, but the third row sums 1 and 1 # and the fourth row sums in pairs. It's a sliding window. row.extend([sum(pair) for pair in zip(last_row, last_row[1:])]) # finally append the final 1 to the outside row.append(1) results.append(row) # add the row to the results. return results 

    uso:

     >>> for i in pascals_triangle(6): ... print(i) ... [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] 

    Sin usar zip, pero usando generador:

     def gen(n,r=[]): for x in range(n): l = len(r) r = [1 if i == 0 or i == l else r[i-1]+r[i] for i in range(l+1)] yield r 

    ejemplo:

     print(list(gen(15))) 

    salida:

     [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1], [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1], [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1], [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1], [1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1]] 

    PANTALLA COMO TRIÁNGULO

    Para dibujarlo en un hermoso triángulo (funciona solo para n <7, más allá de eso se distrae. Ref draw_beautiful para n> 7)

    para n <7

     def draw(n): for p in gen(n): print(' '.join(map(str,p)).center(n*2)+'\n') 

    p.ej:

    draw(10 )

    salida:

      1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 

    para cualquier tamaño

    Ya que necesitamos saber el ancho máximo, no podemos hacer uso del generador.

     def draw_beautiful(n): ps = list(gen(n)) max = len(' '.join(map(str,ps[-1]))) for p in ps: print(' '.join(map(str,p)).center(max)+'\n') 

    Ejemplo (2): funciona para cualquier número:

     draw_beautiful(100) 

    ejemplo de n = 100

    Aquí está mi bash:

     def generate_pascal_triangle(rows): if rows == 1: return [[1]] triangle = [[1], [1, 1]] # pre-populate with the first two rows row = [1, 1] # Starts with the second row and calculate the next for i in range(2, rows): row = [1] + [sum(column) for column in zip(row[1:], row)] + [1] triangle.append(row) return triangle for row in generate_pascal_triangle(6): print row 

    Discusión

    • Las dos primeras filas del triángulo están codificadas
    • La llamada zip() básicamente empareja dos números adyacentes
    • Todavía tenemos que agregar 1 al principio y otro 1 al final porque la llamada zip() solo genera la mitad de la siguiente fila
     def pascal(n): if n==0: return [1] else: N = pascal(n-1) return [1] + [N[i] + N[i+1] for i in range(n-1)] + [1] def pascal_triangle(n): for i in range(n): print pascal(i) 

    Aquí hay una solución recursiva elegante y eficiente. Estoy usando la muy útil biblioteca de herramientas .

     from toolz import memoize, sliding_window @memoize def pascals_triangle(n): """Returns the n'th row of Pascal's triangle.""" if n == 0: return [1] prev_row = pascals_triangle(n-1) return [1, *map(sum, sliding_window(2, prev_row)), 1] 

    pascals_triangle(300) toma aproximadamente 15 ms en un macbook pro (Intel Core i5 a 2,9 GHz). Tenga en cuenta que no puede subir mucho más sin boost el límite de profundidad de recursión predeterminado.

     # combining the insights from Aaron Hall and Hai Vu, # we get: def pastri(n): rows = [[1]] for _ in range(1, n+1): rows.append([1] + [sum(pair) for pair in zip(rows[-1], rows[-1][1:])] + [1]) return rows # thanks! learnt that "shape shifting" data, # can yield/generate elegant solutions. 

    Estoy haciendo trampa de la popular solución de secuencia de fibonacci . Para mí, la implementación del triángulo de Pascal tendría el mismo concepto de fibonacci. En fibonacci usamos un solo número a la vez y lo summos al anterior. En el triángulo de pascal, usa una fila a la vez y súmalo al anterior.

    Aquí hay un ejemplo de código completo :

     >>> def pascal(n): ... r1, r2 = [1], [1, 1] ... degree = 1 ... while degree <= n: ... print(r1) ... r1, r2 = r2, [1] + [sum(pair) for pair in zip(r2, r2[1:]) ] + [1] ... degree += 1 

    Prueba

     >>> pascal(3) [1] [1, 1] [1, 2, 1] >>> pascal(4) [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] >>> pascal(6) [1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] 

    Nota : para tener el resultado como generador, cambie la print(r1) para yield r1 .

     # call the function ! Indent properly , everything should be inside the function def triangle(): matrix=[[0 for i in range(0,20)]for e in range(0,10)] # This method assigns 0's to all Rows and Columns , the range is mentioned div=20/2 # it give us the most middle columns matrix[0][div]=1 # assigning 1 to the middle of first row for i in range(1,len(matrix)-1): # it goes column by column for j in range(1,20-1): # this loop goes row by row matrix[i][j]=matrix[i-1][j-1]+matrix[i-1][j+1] # this is the formula , first element of the matrix gets , addition of i index (which is 0 at first ) with third value on the the related row # replacing 0s with spaces :) for i in range(0,len(matrix)): for j in range(0,20): if matrix[i][j]==0: # Replacing 0's with spaces matrix[i][j]=" " for i in range(0,len(matrix)-1): # using spaces , the triangle will printed beautifully for j in range(0,20): print 1*" ",matrix[i][j],1*" ", # giving some spaces in two sides of the printing numbers triangle() # calling the function 

    imprimiría algo como esto

      1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 

    Estudiante principiante de Python aquí. Aquí está mi bash de hacerlo, un enfoque muy literal, utilizando dos bucles For:

     pascal = [[1]] num = int(input("Number of iterations: ")) print(pascal[0]) # the very first row for i in range(1,num+1): pascal.append([1]) # start off with 1 for j in range(len(pascal[i-1])-1): # the number of times we need to run this loop is (# of elements in the row above)-1 pascal[i].append(pascal[i-1][j]+pascal[i-1][j+1]) # add two adjacent numbers of the row above together pascal[i].append(1) # and cap it with 1 print(pascal[i])