--*********************************************************
-- C(n,r), P(n,r), and nFactorial(n) version 2.0
-- Jim Andrews, August 2004
-- http://vispo.com/lingo/Cnr.htm

--Thanks to Robert Tweed, Valentin Schmidt,
--Andrew Morton, and others on the DirGames-L
--list who helped with this.

-- This is a movie script for Director 8+.

-- API:

--C(n,r) returns the number of combinations
--of n things taken r at a time.

--P(n,r) returns the number of permutations
--of n things taken r at a time.

--nFactorial(n) returns n!=n(n-1)(n-2)...1

--Ctester and Ctester2 are for running C(n,r) in
--batch to test it out and see how it performs in
--terms of execution time.

--Ptester is, similarly, for running P(n,r) in batch to
--see how it performs.


--*********************************************************
--PUBLIC HANDLERS
--*********************************************************


on C(n,r)
  --PUBLIC
  --FUNCTION**********************************************
  --Returns the number of combinations of n things
  --taken r at a time. For instance, if there are
  --four letters A, B, C, D and we select two of them,
  --the possible combinations are AB, AC, AD, BC, BD,
  --CD, ie, there are 6 combinations. Order does not
  --matter.
  --FORMULA************************************************
  --C(n,r)=n! / ((n-r)!r!) = n(n-1)(n-2)...(n-r+1)/r!
  --C(n,r) calculates n/r * (n-1)/(r-1) * ... * (n-r+1)/1
  --Note that 0!=1 and when n>0, C(-n,r)=C(n+r-1,r)*(-1)^r
  --PARAMETERS*********************************************
  --Both n and r must be type integer. If they aren't, 0 is
  --returned. n can be any integer. r>=0 or 0 is returned.
  --abs(n)>=r or 0 is returned.
  --RETURN VALUE*******************************************
  --C(n,r) returns a valid float or INF if the value is too high.
  --INF is an odd float number that stands for 'infinite'.
  --It isn't infinite but just too large for Lingo to handle.
  --If you want to test to see if the result is INF, the way
  --to do it is 'if b=1e309 then', where b is the return value
  --from C(n,r). 1e309 is one of the smallest numbers that
  --is too big for Lingo to handle.
  --C(n,r) returns a valid float for all values of n<1030. When
  --n exceeds 1029, then whether C(n,r) returns a float or
  --INF depends on whether C(n,r) exceeds the maximal Lingo
  --float value which is somewhere around power(10,309)=
  --1e309.
  if integerP(n) and integerP(r) then
    if n> 0 then
      if r > 0 then
        if n>=r then
          a=1.0
          repeat with i= 0 to r-1
            a=a* ((n-i)/float(r-i))
          end repeat
          if a< the maxinteger then
            return a
          else
            if a = 1e309 then
              --Then a is too big a number for Lingo to handle.
              --If you type 'put 1e309' in the Message Window,
              --you see it is in fact INF, ie, a very odd float.
              return a
            else
              return ceiling(a)
            end if
          end if
        else
          --Else n<r
          alert("C(n,r) called with n<r. 0 is returned.")
          return 0
        end if
      else
        --Else r<=0
        if r=0 then
          --Then n>0 and r=0
          return 1
        else
          --Else n>0 and r<0
          alert("C(n,r) called with negative r parameter. 0 is returned.")
          return 0
        end if
      end if
    else
      --Else n<=0
      if n= 0 then
        if r=0 then
          --Then n=0 and r=0
          return 1
        else
          --Else n=0 and r <> 0
          return 0
        end if
      else
        --Else n<0
        --The books define it this way.
        return power(-1,r)*C((-1)*n+r-1,r)
      end if
    end if
  else
    --Else n or r or both are not integers
    alert("C(n,r) called with non-integer parameter(s). 0 is returned.")
    return 0
  end if
end


on P(n,r)
  --PUBLIC
  --FUNCTION**********************************************
  --Returns the number of permutations of n things
  --taken r at a time. For instance, if there are
  --four letters A, B, C, D and we select two of them,
  --the possible permutations are AB, BA, AC, CA, AD, DA,
  --BC, CB, BD, DB, CD, DC, ie, there are 12 permutations.
  --Order does matter.
  --FORMULA************************************************
  --P(n,r)=n! / (n-r)! = n(n-1)(n-2)...(n-r+1)
  --PARAMETERS*********************************************
  --Both n and r must be type integer. If they aren't, 0 is
  --returned. n can be any integer. r>=0 or 0 is returned.
  --abs(n)>=r or 0 is returned.
  --RETURN VALUE*******************************************
  --P(n,r) returns a float or INF if the value is too high.
  --Note that P(n,r) is maximal when r=n, in which case
  --P(n,r)=n! So, like the n! function below, P(n,r) is
  --good for n<=170. Whether P(n,r) returns a float or INF
  --for values of n>170 depends on the value of r.
  if integerP(n) and integerP(r) then
    if n> 0 then
      if r > 0 then
        if n>=r then
          a=1.0
          repeat with i= 0 to r-1
            a=a* (n-i)
          end repeat
          return a
        else
          --Else abs(n)<r
          alert("P(n,r) called with n<r. 0 is returned.")
          return 0
        end if
      else
        --Else r<=0
        if r=0 then
          --Then n>0 and r=0
          return 1
        else
          --Else n>0 and r<0
          alert("P(n,r) called with negative r parameter. 0 is returned.")
          return 0
        end if
      end if
    else
      --Else n<=0
      if n= 0 then
        if r=0 then
          --Then n=0 and r=0
          return 1
        else
          --Else n=0 and r <> 0
          return 0
        end if
      else
        --Else n<0
        return power(-1,r)*P((-1)*n+r-1,r)
      end if
    end if
  else
    --Else n or r or both are not integers
    alert("P(n,r) called with non-integer parameter(s). 0 is returned.")
    return 0
  end if
end


on nFactorial(n)
  --PUBLIC
  --FUNCTION**********************************************
  --Returns n! = n(n-1)...1
  --Note that 0!=1.
  --PARAMETER*********************************************
  --n is an integer >=0. If not, 0 is returned.
  --RETURN VALUE*******************************************
  --Returns a float. nFactorial(n) is good for n<=170.
  --Returns INF for values of n > 170.
  if integerP(n) then
    if n>0 then
      a=1.0
      repeat with i=2 to n
        a=a*i
      end repeat
      return a
    else
      --Else n<=0
      if n=0 then
        --0! is defined to be 1.
        return 1
      else
        --n<0, so we return 0
        alert("nFactorial called with negative value of n. 0 is returned.")
        return 0
      end if
    end if
  else
    --Else n is not an integer
    alert("nFactorial called with non-integer parameter. 0 is returned.")
    return 0
  end if
end nFactorial


on Ctester(n1, n2)
  --PUBLIC
  --This was written to test C(n,r).
  --This runs C(n,r)   n2 - n1   times.
  --For instance, if n1=4 and n2=10, tester will compute
  --C(4,2), C(5,2), C(6,3), C(7/3), C(8,4), C(9,4), and C(10,5)
  --and display the time each took to compute.
  --In each case, r is basically half of n.
  thetext=""
  repeat with i=n1 to n2
    n=i
    r=abs(i/2)
    startTime=the milliseconds
    theResult=C(n,r)
    theEndTime=the milliseconds - startTime
    theText=theText & "C(" & string(n) & "," & string(r) & ")="  & \
    string(theResult) &  "  time: " & string(theEndTime) & " ms" & RETURN
  end repeat
  put theText
end


on Ctester2(n1, n2, r)
  --PUBLIC
  --This was written to test C(n,r).
  --This runs C(n,r)   n2 - n1   times.
  --For instance, if n1=4 and n2=10, and r=3, Ctester2 will compute
  --C(4,3), C(5,3), C(6,3), C(7,3), C(8,3), C(9,3), and C(10,3)
  --and display the time each took to compute.
  thetext=""
  repeat with i=n1 to n2
    n=i
    startTime=the milliseconds
    theResult=C(n,r)
    theEndTime=the milliseconds - startTime
    theText=theText & "C(" & string(n) & "," & string(r) & ")="  & \
    string(theResult) &  "  time: " & string(theEndTime) & " ms" & RETURN
  end repeat
  put theText
end


on Ptester(n1, n2)
  --PUBLIC
  --This was written to test P(n,r).
  --This runs P(n,r)   n2 - n1   times.
  --For instance, if n1=4 and n2=10, tester will compute
  --P(4,2), P(5,2), P(6,3), P(7/3), P(8,4), P(9,4), and P(10,5)
  --and display the time each took to compute.
  thetext=""
  repeat with i=n1 to n2
    n=i
    r=abs(i/2)
    startTime=the milliseconds
    theResult=P(n,r)
    theEndTime=the milliseconds - startTime
    theText=theText & "P(" & string(n) & "," & string(r) & ")="  & \
    string(theResult) &  "  time: " & string(theEndTime) & " ms" & RETURN
  end repeat
  put theText
end


--*********************************************************
--PRIVATE HANDLERS
--*********************************************************


on ceiling(x)
  --Takes a positive float argument
  --and returns the ceiling value.
  --For instance, if a float is b.c,
  --where c is the decimal part, then
  --if c is 0, ceiling(b.c) = b.c, but
  --if c is not 0, then ceiling(b.c)=
  --b + 1 as a float value.
  y=rnd(x)
  if y < x then
    return y+1
  else
    return y
  end if
end


on rnd (x)
  --This takes a float argument
  --and truncates any decimal
  --as the return value.
  --So if a float is b.c where
  --c is the decimal portion,
  --then rnd(a.b) returns a.0
  fp = the floatprecision
  the floatprecision = 0
  r = value(string(x))
  the floatprecision = fp
  return r
end



V I S P O