Urban Hafner

CTM: Exercises of Chapter 1 (Exercise 2)

Posted by urban Sat, 02 Apr 2005 11:28:00 GMT

The problem

Calculating combinations. Section 1.3 defines the function Comb to calculate combinations. This function is not very efficient because it might require calculating very large factorials. The purpose of this exercise is to write a more efficient version of Comb.

(a) As a first step, use the following alternative definition to write a more efficient function (imagine a nicely formated formula):

Calculate the numerator and denominator separately and then divide them. Make sure the result is 1 when k=0.

(b) As a second step, use the following identity:

to increase efficiency even more. That is, if k > n/2, then do the calculation with n-k instead of with k.

My solution

(a) Fact and AtoB are helper functions.

declare
fun {Fact N}
   if N==0 then 1 else N*{Fact N-1} end
end

declare
fun {AtoB A B}
   if A < B then
      1
   else
      if A == B then A else A*{AtoB A-1 B} end
   end
end

declare
fun {FasterComb N K}
   {AtoB N N-K+1} div {Fact K}
end

(b) The function FasterComb is from part (a).

declare
fun {FastComb N K}
   if K > (N div 2) then
      {FastComb N N-K}
   else
      {FasterComb N K}
   end
end