From: Brian Candler <B.Candler@...>
Date: 2007-05-26T23:09:43+09:00
Subject: Re: Ruby Math (nPr, nCr)

On Sat, May 26, 2007 at 10:57:16AM +0900, Ari Brown wrote:
> # Pascals triangle
> 
> class Integer
> 
>   def self.nPr(r)
>     numerator   = factorial(self)
>     denominator = factorial(self - r)
> 
>     @permutations = numerator / denominator
>   end
> 
>   def self.nCr(r)
>     numerator   = factorial(self)
>     denominator = factorial(r) * factorial(self - r)
> 
>     @combinations = numberator / denominator
>   end
> 
> end

Of course Ruby has Bignums, but you could make the program more efficient by
not calculating such enormous intermediate values and then dividing them.

I suggest you cancel out the terms which are common to the numerator and
denominator.

That is, 9C4 is 9!/5!/!4!, but 9!/5! is 9*8*7*6, so the result is
9*8*7*6/4*3*2*1. Also, you can swap r and n-r to minimise the calculation.

Example:

def Math.nCr(n,r)
  a, b = r, n-r
  a, b = b, a if a < b  # a is the larger
  numer = (a+1..n).inject(1) { |t,v| t*v }  # n!/r!
  denom = (2..b).inject(1) { |t,v| t*v }    # (n-r)!
  numer/denom
end

(0..9).each { |r| puts Math.nCr(9,r) }

As for making these instance variables of Integer (without self.): that's
fine, but I'd suggest you make them class methods of Math or of your own
module. Whilst

   Math.nCr(9,4)

is a bit more long-winded to type than 9.nCr(4), it avoids cluttering
Integer with more methods.

Regards,

Brian.