Brian Candler
5/26/2007 2:10:00 PM
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.