Module: LilUtils::Misc::Pascal

Defined in:
lib/lilutils/misc/pascal.rb

Class Method Summary collapse

Class Method Details

.row(n) ⇒ Array

Returns the nth row of the Pascal’s triangle as an array of n+1 elements. This is an O(n) algorithm. Uses: nCr = nCr-1*(n-r+1)/r which calculates an element using the previous element (which is already initialized or calculated). Thus, it does not throw away any computation. The constant factors of this alogirthm are also good (~0.5).

Parameters:

  • n (Integer) —

    starts at 1

Returns:

  • (Array) —

    of Integers representing numbers in given row.

Raises:

  • (ArgumentError) 


11
12
13
14
15
16
17
18
19
 
# File 'lib/lilutils/misc/pascal.rb', line 11

def self.row(n)
  raise ArgumentError, "#{n} is not valid" if !n.is_a?(Integer) || n < 1
  len = n == 1 ? 1 : n + 1
  a = Array.new(len); a[0] = a[-1] = 1 # by definition
  1.upto n/2 do |r|
    a[r] = a[-r-1] = a[r-1] * (n-r+1)/r
  end
  a
end