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 , which is 10.
This formula is recommended:
C
<lang c>#include <stdio.h>
- 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
<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>
J
Solution:
The dyadic form of the primitive !
([Out of]) evaluates binomial coefficients directly.
Example usage: <lang j> 3 ! 5 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
<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
JavaScript
<lang javascript>function binom(n, k) {
var coeff = 1; for (var i = n-k+1; i <= n; i++) coeff *= i; for (var i = 1; i <= k; i++) coeff /= i; return coeff;
} print(binom(5,3));</lang>
10
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
<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>
PL/I
<lang PL/I> binomial_coefficients:
procedure options (main); declare (n, k) fixed;
get (n, k); put (coefficient(n, k));
coefficient: procedure (n, k) returns (fixed decimal (15));
declare (n, k) fixed; return (fact(n)/ (fact(n-k) * fact(k)) );
end coefficient;
fact: procedure (n) returns (fixed decimal (15));
declare n fixed; declare i fixed, f fixed decimal (15); f = 1; do i = 1 to n; f = f * i; end; return (f);
end fact; end binomial_coefficients; </lang> Output: <lang>
10
</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
<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
<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 thequotient
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. Thefactorial
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 theproduct
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>