Evaluate binomial coefficients

Evaluate binomial coefficients
You are encouraged to solve this task according to the task description, using any language you may know.

This programming task, is to calculate ANY binomial coefficient.

However, it has to be able to output ${\binom {5}{3}}$, which is 10.

This formula is recommended:

${\binom {n}{k}}={\frac {n!}{(n-k)!k!}}={\frac {n(n-1)(n-2)\ldots (n-k+1)}{k(k-1)(k-2)\ldots 1}}$

C

<lang c>#include <stdio.h>

1. include <stdlib.h>

int factorial(int); int choose(int, int);

int main(void) {

       printf("%d\n", choose(5, 3));

       return EXIT_SUCCESS;

}

int factorial(int n) {

       int result;
       int i;

       result = 1;
       for (i = 1; i <= n; i++) {
               result *= i;
       }

       return result;

}

int choose(int n, int k) {

       int result;

       result = factorial(n) / (factorial(k) * factorial(n - k));

       return result;

}</lang> Output: <lang>10</lang>

C++

<lang cpp>double Factorial(double nValue)

  {
      double result = nValue;
      double result_next;
      double pc = nValue;
      do
      {
          result_next = result*(pc-1);
          result = result_next;
          pc--;
      }while(pc>2);
      nValue = result;
      return nValue;
  }

double EvaluateBinomialCoefficient(double nValue, double nValue2)

  {
      double result;

      result = (Factorial(nValue))/(Factorial(nValue2)*Factorial((nValue - nValue2)));
      nValue2 = result;
      return nValue2;
  }</lang>

Implementation: <lang cpp>int main() {

   cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< EvaluateBinomialCoefficient(5,3);
   cin.get();

}</lang>

Output:

The Binomial Coefficient of 5, and 3, is equal to: 10

F#

<lang fsharp> let factorial n = List.fold (*) 1 [1..n] let choose n k =

   (factorial n)/(factorial(n-k)*factorial(k))

</lang>

Forth

<lang forth>: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;

5  3 choose .   \ 10

33 17 choose . \ 1166803110</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>program test_choose

 implicit none

 write (*, '(i0)') choose (5, 3)

contains

 function factorial (n) result (res)

   implicit none
   integer, intent (in) :: n
   integer :: res
   integer :: i

   res = product ((/(i, i = 1, n)/))

 end function factorial

 function choose (n, k) result (res)

   implicit none
   integer, intent (in) :: n
   integer, intent (in) :: k
   integer :: res

   res = factorial (n) / (factorial (k) * factorial (n - k))

 end function choose

end program test_choose</lang> Output: <lang>10</lang>

Java

<lang java>public class Binom {

   public static double fact(double a) {
       double retVal = 1;
       for (double i = a; i > 1; i--) {
           retVal *= i;
       }
       return retVal;
   }

   public static double binomialCoeff(double n, double k) {
       return (fact(n)) / (fact(k) * fact((n - k)));
   }

   public static void main(String[] args){
       System.out.println(binomialCoeff(5, 3));
   }

}</lang> Output:

10.0

Translation of: Python

<lang java>public class Binom {

   public static double binomCoeff(double n, double k) {
       double result = 1;
       for (int i = 1; i < k + 1; i++) {
           result *= (n - i + 1) / i;
       }
       return result;
   }

   public static void main(String[] args) {
       System.out.println(binomCoeff(5, 3));
   }

} </lang> Output:

10.0

Logo

<lang logo>to choose :n :k

 if :k = 0 [output 1]
 output (choose :n :k-1) * (:n - :k + 1) / :k

end

show choose 5 3  ; 10 show choose 60 30 ; 1.18264581564861e+17</lang>

Oz

Translation of: Python

<lang oz>declare

 fun {BinomialCoeff N K}
    {List.foldL {List.number 1 K 1}
     fun {$ Z I}
        Z * (N-I+1) div I
     end
     1}
 end

in

 {Show {BinomialCoeff 5 3}}</lang>

PureBasic

<lang PureBasic>Procedure Factor(n)

 Protected Result=1
 While n>0
   Result*n
   n-1
 Wend
 ProcedureReturn Result

EndProcedure

Macro C(n,k)

 (Factor(n)/(Factor(k)*factor(n-k)))

EndMacro

If OpenConsole()

 Print("Enter value n: "): n=Val(Input())
 Print("Enter value k: "): k=Val(Input())
 PrintN("C(n,k)= "+str(C(n,k)))
 
 Print("Press ENTER to quit"): Input()
 CloseConsole()

EndIf</lang> Example

Enter value n: 5
Enter value k: 3
C(n,k)= 10

Python

Straight-forward implementation: <lang python>def binomialCoeff(n, k):

   result = 1
   for i in range(1, k+1):
       result = result * (n-i+1) / i
   return result

if __name__ == "__main__":

   print(binomialCoeff(5, 3))</lang>

Output:

10

Alternate implementation <lang python>from operator import mul def comb(n,r):

    calculate nCr - the binomial coefficient
   >>> comb(3,2)
   3
   >>> comb(9,4)
   126
   >>> comb(9,6)
   84
   >>> comb(20,14)
   38760
   
   
   if r > n-r:  # for smaller intermediate values
       r = n-r
   return int( reduce( mul, range((n-r+1), n+1), 1) /
     reduce( mul, range(1,r+1), 1) )</lang>

Ruby

Translation of: Tcl

Works with: Ruby version 1.8.7+

<lang ruby>class Integer

 # binomial coefficient: n C k
 def choose(k)
   # n!/(n-k)!
   pTop = (self-k+1 .. self).inject(1, &:*) 
   # k!
   pBottom = (2 .. k).inject(1, &:*)
   pTop / pBottom
 end

end

p 5.choose(3) p 60.choose(30)</lang> result

10
118264581564861424

Scheme

Works with: Scheme version R$^{5}$RS

<lang scheme>(define (factorial n)

 (define (*factorial n acc)
   (if (zero? n)
       acc
       (*factorial (- n 1) (* acc n))))
 (*factorial n 1))

(define (choose n k)

 (/ (factorial n) (* (factorial k) (factorial (- n k)))))

(display (choose 5 3)) (newline)</lang> Output: <lang>10</lang>

Tcl

This uses exact arbitrary precision integer arithmetic. <lang tcl>package require Tcl 8.5 proc binom {n k} {

   # Compute the top half of the division; this is n!/(n-k)!
   set pTop 1
   for {set i $n} {$i > $n - $k} {incr i -1} {

set pTop [expr {$pTop * $i}]

   }

   # Compute the bottom half of the division; this is k!
   set pBottom 1
   for {set i $k} {$i > 1} {incr i -1} {

set pBottom [expr {$pBottom * $i}]

   }

   # Integer arithmetic divide is correct here; the factors always cancel out
   return [expr {$pTop / $pBottom}]

}</lang> Demonstrating: <lang tcl>puts "5_C_3 = [binom 5 3]" puts "60_C_30 = [binom 60 30]"</lang> Output:

5_C_3 = 10
60_C_30 = 118264581564861424

Ursala

A function for computing binomial coefficients (choose) is included in a standard library, but if it weren't, it could be defined in one of the following ways, starting from the most idiomatic. <lang Ursala>#import nat

choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~</lang> The standard library functions quotient, product and predecessor pertain to natural numbers in the obvious way.

• choose is defined using the recursive conditional combinator (^?) as a function taking a pair of numbers, with the predicate ~&ar testing whether the number on the right side of the pair is non-zero.
• If the predicate does not hold (implying the right side is zero), then a constant value of 1 is returned.
• If the predicate holds, the function given by the rest of the expression executes as follows.
• First the predecessor of both sides (~~) of the argument is taken.
• Then a recursive call (^|R) is made to the whole function (~&) with the pair of predecessors passed to it as an argument.
• The result returned by the recursive call is multiplied (product) by the left side of the original argument (~&al).
• The product of these values is then divided (quotient) by the right side (~&ar) of the original argument and returned as the result.

Here is a less efficient implementation more closely following the formula above. <lang Ursala>choose = quotient^/factorial@l product+ factorial^~/difference ~&r</lang>

• choose is defined as the quotient of the results of a pair (^) of functions.
• The left function contributing to the quotient is the factorial of the left side (@l) of the argument, which is assumed to be a pair of natural numbers. The factorial function is provided in a standard library.
• The right function contributing to the quotient is the function given by the rest of the expression, which applies to the whole pair as follows.
• It begins by forming a pair of numbers from the argument, the left being their difference obtained by subtraction, and the right being the a copy of the right (~&r) side of the argument.
• The factorial function is applied separately to both results (^~).
• A composition (+) of this function with the product function effects the multiplication of the two factorials, to complete the other input to the quotient.

Here is an equivalent implementation using pattern matching, dummy variables, and only the apply-to-both (~~) operator. <lang Ursala>choose("n","k") = quotient(factorial "n",product factorial~~ (difference("n","k"),"k"))</lang> test program: <lang Ursala>#cast %nL

main = choose* <(5,3),(60,30)></lang> output:

<10,118264581564861424>