Python 的帕斯卡三角形
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24093387/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Pascal's Triangle for Python
提问by louie mcconnell
As a learning experience for Python, I am trying to code my own version of Pascal's triangle. It took me a few hours (as I am just starting), but I came out with this code:
作为 Python 的学习经验，我正在尝试编写自己版本的 Pascal 三角形。我花了几个小时（因为我才刚刚开始），但我得出了以下代码：
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)
which returns
返回
[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]
However, I have no idea where to go from here. I have been banging my head against the wall for hours. I want to emphasize that I do NOT want you to do it for me; just push me in the right direction. As a list, my code returns
但是，我不知道从哪里开始。几个小时以来，我一直在用头撞墙。我想强调的是，我不希望你为我做这件事；把我推向正确的方向。作为列表，我的代码返回
[[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]]
Thanks.
谢谢。
EDIT: I took some good advice, and I completely rewrote my code, but I am now running into another problem. Here is my code.
编辑：我接受了一些很好的建议，我完全重写了我的代码，但我现在遇到了另一个问题。这是我的代码。
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)
However, I am finding that the output is a bit undesirable:
但是，我发现输出有点不理想：
[1, 1, 1, 1, 2, 1, 1, 3, 3, 1]
How can I fix this?
我怎样才能解决这个问题？
采纳答案by Aaron Hall
OK code review:
OK 代码：
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)
prints:
印刷：
[1]
[1, 1]
[1, 2, 1]
Explanation of Pascal's triangle:
帕斯卡三角形的解释：
This is the formula for "n choose k"(i.e. how many different ways (disregarding order), from an ordered list of n items, can we choose k items):
这是“n选k”的公式（即有多少种不同的方式（不考虑顺序），从n个项目的有序列表中，我们可以选择k个项目）：
from math import factorial
def combination(n, k):
"""n choose k, returns int"""
return int((factorial(n)) / ((factorial(k)) * factorial(n - k)))
A commenter asked if this is related to itertools.combinations - indeed it is. "n choose k" can be calculated by taking the length of a list of elements from combinations:
一位评论者询问这是否与 itertools.combinations 相关 - 确实如此。“n 选择 k”可以通过从组合中获取元素列表的长度来计算：
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
Let's see this demonstrated:
让我们看看这个演示：
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]]
We can avoid repeating ourselves with a nested list comprehension:
我们可以避免重复使用嵌套列表推导式：
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]]
Recursively defined:
递归定义：
We can define this recursively (a less efficient, but perhaps more mathematically elegant definition) using the relationships illustrated by the triangle:
我们可以使用三角形所示的关系递归地定义它（一个效率较低，但可能在数学上更优雅的定义）：
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)
And for fun, you can see each row take progressively longer to execute, because each row has to recompute nearly each element from the prior row twice each time:
有趣的是，您可以看到每一行的执行时间越来越长，因为每行每次都必须重新计算前一行中的几乎每个元素两次：
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 to quit when you get tired of watching it, it gets very slow very fast...
当你看腻了Ctrl-C退出，它变得非常慢非常快......
回答by Aaron Hall
I know you want to implement yourself, but the best way for me to explain is to walk through an implementation. Here's how I would do it, and this implementation relies on my fairly complete knowledge of how Python's functions work, so you probably won't want to use this code yourself, but it may get you pointed in the right direction.
我知道您想自己实现，但对我来说最好的解释方法是遍历一个实现。下面是我的做法，这个实现依赖于我对 Python 函数如何工作的相当完整的了解，所以你可能不想自己使用这段代码，但它可能会让你指向正确的方向。
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
usage:
用法：
>>> 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]
回答by Hai Vu
Here is my attempt:
这是我的尝试：
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
Discussion
讨论
- The first two rows of the triangle is hard-coded
- The
zip()call basically pairs two adjacent numbers together - We still have to add 1 to the beginning and another 1 to the end because the
zip()call only generates the middle of the next row
- 三角形的前两行是硬编码的
- 该
zip()呼叫基本上将两个相邻的号码配对在一起 - 我们仍然必须在开头加 1，在结尾加 1，因为
zip()调用只生成下一行的中间
回答by ssgam
# 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.
回答by Abdel
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)
回答by Niamatullah Bakhshi
# 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
would print something like this
会打印这样的东西
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
回答by Aziz Alto
I am cheating from the popular fibonacci sequencesolution. To me, the implementation of Pascal's triangle would have the same concept of fibonacci's. In fibonacci we use a single number at a time and add it up to the previous one. In pascal's triangle use a row at a time and add it up to the previous one.
我从流行的斐波那契数列解决方案中作弊。对我来说，帕斯卡三角形的实现与斐波那契三角形的概念相同。在斐波那契中，我们一次使用一个数字并将其与前一个数字相加。在帕斯卡的三角形中，一次使用一行并将其与前一行相加。
Here is a complete code example:
这是一个完整的代码示例：
>>> 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
Test
测试
>>> 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]
Note: to have the result as a generator, change print(r1)to yield r1.
注意：要将结果作为生成器，请更改print(r1)为yield r1.
回答by user3932000
Beginner Python student here. Here's my attempt at it, a very literal approach, using two For loops:
初学者 Python 学生在这里。这是我的尝试，一种非常直接的方法，使用两个 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])
回答by MortalViews
Without using zip, but using generator:
不使用 zip，而是使用生成器：
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
example:
例子：
print(list(gen(15)))
output:
输出：
[[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]]
DISPLAY AS TRIANGLE
显示为三角形
To draw it in beautiful triangle(works only for n < 7, beyond that it gets distroted. ref draw_beautiful for n>7)
将它绘制成漂亮的三角形（仅适用于 n < 7，除此之外它会被破坏。ref draw_beautiful for n>7）
for n < 7
对于 n < 7
def draw(n):
for p in gen(n):
print(' '.join(map(str,p)).center(n*2)+'\n')
eg:
例如：
draw(10)
draw(10)
output:
输出：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
for any size
任何尺寸
since we need to know the max width, we can't make use of generator
因为我们需要知道最大宽度，所以我们不能使用生成器
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')
example (2) : works for any number:
示例（2）：适用于任何数字：
draw_beautiful(100)
回答by fredcallaway
Here is an elegant and efficient recursive solution. I'm using the very handy toolzlibrary.
这是一个优雅而有效的递归解决方案。我正在使用非常方便的toolz库。
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)takes about 15 ms on a macbook pro (2.9 GHz Intel Core i5). Note that you can't go much higher without increasing the default recursion depth limit.
pascals_triangle(300)在 macbook pro（2.9 GHz Intel Core i5）上大约需要 15 毫秒。请注意，在不增加默认递归深度限制的情况下，您无法进一步提高。
