How to efficiently calculate a row in pascal's

Question

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?

Answer 1

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;
}

Answer 2

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.

Answer 3

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))

Answer 4

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]

Answer 5

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

Answer 6

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