How to efficiently calculate a row in pascal's

问题:

I'm interested in finding the nth row of pascal triangle (not a specific element but the whole row itself). What would be the most efficient way to do it?

I thought about the conventional way to construct the triangle by summing up the corresponding elements in the row above which would take:

1 + 2 + .. + n = O(n^2)

Another way could be using the combination formula of a specific element:

c(n, k) = n! / (k!(n-k)!)

for each element in the row which I guess would take more time the the former method depending on the way to calculate the combination. Any ideas?

回答1:

>>> def pascal(n):
...   line = [1]
...   for k in range(n):
...     line.append(line[k] * (n-k) / (k+1))
...   return line
... 
>>> pascal(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

This uses the following identity:

C(n,k+1) = C(n,k) * (n-k) / (k+1)

So you can start with C(n,0) = 1 and then calculate the rest of the line using this identity, each time multiplying the previous element by (n-k) / (k+1).

回答2:

A single row can be calculated as follows:

First compute 1.               -> N choose 0
Then N/1                       -> N choose 1
Then N*(N-1)/1*2               -> N choose 2
Then N*(N-1)*(N-2)/1*2*3       -> N choose 3
.....

Notice that you can compute the next value from the previous value, by just multipyling by a single number and then dividing by another number.

This can be done in a single loop. Sample python.

def comb_row(n):
   r = 0
   num = n
   cur = 1
   yield cur
   while r <= n:
      r += 1  
      cur = (cur* num)/r
      yield cur
      num -= 1

回答3:

The most efficient approach would be:

std::vector<int> pascal_row(int n){
    std::vector<int> row(n+1);
    row[0] = 1; //First element is always 1
    for(int i=1; i<n/2+1; i++){ //Progress up, until reaching the middle value
        row[i] = row[i-1] * (n-i+1)/i;
    }
    for(int i=n/2+1; i<=n; i++){ //Copy the inverse of the first part
        row[i] = row[n-i];
    }
    return row;
}

回答4:

here is a fast example implemented in go-lang that calculates from the outer edges of a row and works it's way to the middle assigning two values with a single calculation...

package main

import "fmt"

func calcRow(n int) []int {
    // row always has n + 1 elements
    row := make( []int, n + 1, n + 1 )

    // set the edges
    row[0], row[n] = 1, 1

    // calculate values for the next n-1 columns
    for i := 0; i < int(n / 2) ; i++ {
        x := row[ i ] * (n - i) / (i + 1)

        row[ i + 1 ], row[ n - 1 - i ] = x, x
    }

    return row
}

func main() {
    for n := 0; n < 20; n++ {
        fmt.Printf("n = %d, row = %v\n", n, calcRow( n ))
    }
}

the output for 20 iterations takes about 1/4 millisecond to run...

n = 0, row = [1]
n = 1, row = [1 1]
n = 2, row = [1 2 1]
n = 3, row = [1 3 3 1]
n = 4, row = [1 4 6 4 1]
n = 5, row = [1 5 10 10 5 1]
n = 6, row = [1 6 15 20 15 6 1]
n = 7, row = [1 7 21 35 35 21 7 1]
n = 8, row = [1 8 28 56 70 56 28 8 1]
n = 9, row = [1 9 36 84 126 126 84 36 9 1]
n = 10, row = [1 10 45 120 210 252 210 120 45 10 1]
n = 11, row = [1 11 55 165 330 462 462 330 165 55 11 1]
n = 12, row = [1 12 66 220 495 792 924 792 495 220 66 12 1]
n = 13, row = [1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1]
n = 14, row = [1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1]
n = 15, row = [1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1]
n = 16, row = [1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1]
n = 17, row = [1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1]
n = 18, row = [1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1]
n = 19, row = [1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1]

回答5:

An easy way to calculate it is by noticing that the element of the next row can be calculated as a sum of two consecutive elements in the previous row.

[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]

For example 6 = 5 + 1, 15 = 5 + 10, 1 = 1 + 0 and 20 = 10 + 10. This gives a simple algorithm to calculate the next row from the previous one.

def pascal(n):
    row = [1]
    for x in xrange(n):
        row = [l + r for l, r in zip(row + [0], [0] + row)]
    # print row
    return row

print pascal(10)

回答6:

In Scala Programming: i would have done it as simple as this:

def pascal(c: Int, r: Int): Int = c match {
    case 0 => 1
    case `c` if c >= r => 1
    case _ => pascal(c-1, r-1)+pascal(c, r-1)
}

I would call it inside this:

for (row <- 0 to 10) {
    for (col <- 0 to row)
        print(pascal(col, row) + " ")
    println()
}

resulting to:

. 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

To explain step by step:

Step 1: We make sure that if our column is the first one we always return figure 1.

Step 2: Since each X-th row there are X number of columns. So we say that; the last column X is greater than or equal to X-th row, then the return figure 1.

Step 3: Otherwise, we get the sum of the repeated pascal of the column just before the current one and the row just before the current one ; and the pascal of that column and the row just before the current one.

Good Luck.

回答7:

The most efficient way to calculate a row in pascal's triangle is through convolution. First we chose the second row (1,1) to be a kernel and then in order to get the next row we only need to convolve curent row with the kernel.

So convolution of the kernel with second row gives third row [1 1]*[1 1] = [1 2 1], convolution with the third row gives fourth [1 2 1]*[1 1] = [1 3 3 1] and so on

This is a function in julia-lang (very simular to matlab):

function binomRow(n::Int64)
baseVector = [1] #the first row is equal to 1. 
kernel = [1,1]   #This is the second row and a kernel. 
row = zeros(n)
for i = 1 : n
    row = baseVector 
    baseVector = conv(baseVector, kernel) #convoltion with kernel
end
return row::Array{Int64,1}
end

回答8:

In Ruby, the following code will print out the specific row of Pascals Triangle that you want:

def row(n)
  pascal = [1]
  if n < 1
    p pascal
    return pascal
  else
    n.times do |num|
      nextNum = ((n - num)/(num.to_f + 1)) * pascal[num]
      pascal << nextNum.to_i
    end
  end
  p pascal
end

Where calling row(0) returns [1] and row(5) returns [1, 5, 10, 10, 5, 1]

回答9:

Here is the another best and simple way to design a Pascal Triangle dynamically using VBA.

`1
11
121
1331
14641`

`Sub pascal()
Dim book As Excel.Workbook
Dim sht As Worksheet
Set book = ThisWorkbook
Set sht = book.Worksheets("sheet1")
a = InputBox("Enter the Number", "Fill")
For i = 1 To a
    For k = 1 To i
        If i >= 2 And k >= 2 Then
            sht.Cells(i, k).Value = sht.Cells(i - 1, k - 1) + sht.Cell(i-  1, k)
        Else
            sht.Cells(i, k).Value = 1
        End If
    Next k
Next i
End Sub`

回答10:

I used Ti-84 Plus CE

The use of –> in line 6 is the store value button

Forloop syntax is 
:For(variable, beginning, end [, increment])
:Commands
:End

nCr syntax is 
:valueA nCr valueB

List indexes start at 1 so that's why i set it to R+1

N= row
R= column

PROGRAM: PASCAL
:ClrHome
:ClrList L1
:Disp "ROW
:Input N
:For(R,0,N,1)
:N nCr R–>L1(R+1)
:End
:Disp L1

This is the fastest way I can think of to do this in programming (with a ti 84) but if you mean to be able to calculate the row using pen and paper then just draw out the triangle cause doing factorals are a pain!

回答11:

Here's an O(n) space-complexity solution in Python:

def generate_pascal_nth_row(n):
    result=[1]*n
    for i in range(n):
        previous_res = result.copy()
        for j in range(1,i):
            result[j] = previous_res[j-1] + previous_res[j]
    return result

print(generate_pascal_nth_row(6))