Evaluate binomial coefficients: Difference between revisions
(+Icon+Unicon) |
|||
Line 259: | Line 259: | ||
<lang haskell>> 5 `choose` 3 |
<lang haskell>> 5 `choose` 3 |
||
10</lang> |
10</lang> |
||
== Icon and Unicon == |
|||
==={{header|Icon}}=== |
|||
<lang Icon>link math, factors |
|||
procedure main() |
|||
write("choose(5,3)=",binocoef(5,3)) |
|||
end</lang> |
|||
Output: |
|||
<pre>choose(5,3)=10</pre> |
|||
{{libheader|Icon Programming Library}} |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/math.icn math provides binocoef] and |
|||
[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors provides factorial]. |
|||
<lang Icon>procedure binocoef(n, k) #: binomial coefficient |
|||
k := integer(k) | fail |
|||
n := integer(n) | fail |
|||
if (k = 0) | (n = k) then return 1 |
|||
if 0 <= k <= n then |
|||
return factorial(n) / (factorial(k) * factorial(n - k)) |
|||
else fail |
|||
end |
|||
procedure factorial(n) #: return n! (n factorial) |
|||
local i |
|||
n := integer(n) | runerr(101, n) |
|||
if n < 0 then fail |
|||
i := 1 |
|||
every i *:= 1 to n |
|||
return i |
|||
end</lang> |
|||
==={{header|Unicon}}=== |
|||
This Icon solution works in Unicon. |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 19:39, 4 July 2010
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:
ALGOL 68
Iterative - unoptimised
- note: This specimen retains the original C coding style.
<lang algol68>PROC factorial = (INT n)INT: (
INT result; result := 1; FOR i TO n DO result *:= i OD; result
);
PROC choose = (INT n, INT k)INT: (
INT result;
- Note: code can be optimised here as k < n #
result := factorial(n) OVER (factorial(k) * factorial(n - k)); result
);
test:(
print((choose(5, 3), new line))
)</lang> Output:
+10
AutoHotkey
<lang autohotkey>MsgBox, % Round(BinomialCoefficient(5, 3))
- ---------------------------------------------------------------------------
BinomialCoefficient(n, k) {
- ---------------------------------------------------------------------------
r := 1 Loop, % k < n - k ? k : n - k { r *= n - A_Index + 1 r /= A_Index } Return, r
}</lang> Message box shows:
10
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
C#
<lang csharp>using System;
namespace BinomialCoefficients {
class Program { static void Main(string[] args) { int n = 5, k = 3; int result = fact(n) / (fact(k) * fact(n - k)); Console.WriteLine("The Binomial Coefficient of {0}, and {1}, is equal to: {2}", n, k, result); }
static int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); } }
}</lang>
D
<lang d>import std.stdio; import std.bigint ;
T bino(T)(T n , T k) {
if (k > n/2) k = n - k ; T bc = n - k + 1 ; for(T i = 2 ; i <= k ; i++) bc = ( bc * (n - k + i)) / i ; return bc ;
}
void main() {
BigInt b100 = "100", b50 = "50" ;
writefln("( 5 3) = %d", bino(5, 3)) ; writefln("(100 2) = %d", bino(100, 2)) ; writefln("(100 98) = %d", bino(100, 98)) ; bino(b100, b50).toString((const(char)[] s) { writefln("(100 50) = %s", s) ;}, "%s") ;
}</lang>
Erlang
<lang erlang> choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) ->
cohoose(N, K, 1, 1).
choose(N, K, K, Acc) ->
(Acc * (N-K+1)) div K;
choose(N, K, I, Acc) ->
choose(N, K, I+1, (Acc * (N-I+1)) div I).
</lang>
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>
Go
<lang go>package main import "fmt" import "big"
func main() {
fmt.Println(new(big.Int).Binomial(5, 3).Int64())
}</lang>
Haskell
The only trick here is realizing that everything's going to divide nicely, so we can use div instead of (/).
<lang haskell> choose :: (Integral a) => a -> a -> a choose n k = product([k+1..n]) `div` product([1..n-k]) </lang>
<lang haskell>> 5 `choose` 3 10</lang>
Icon and Unicon
Icon
<lang Icon>link math, factors
procedure main() write("choose(5,3)=",binocoef(5,3)) end</lang> Output:
choose(5,3)=10
math provides binocoef and factors provides factorial.
<lang Icon>procedure binocoef(n, k) #: binomial coefficient
k := integer(k) | fail n := integer(n) | fail
if (k = 0) | (n = k) then return 1
if 0 <= k <= n then return factorial(n) / (factorial(k) * factorial(n - k)) else fail
end
procedure factorial(n) #: return n! (n factorial)
local i
n := integer(n) | runerr(101, n)
if n < 0 then fail
i := 1
every i *:= 1 to n
return i
end</lang>
Unicon
This Icon solution works in Unicon.
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>
MATLAB
This is a built-in function in MATLAB called "nchoosek(n,k)". But, this will only work for scalar inputs. If "n" is a vector then "nchoosek(v,k)" finds all combinations of choosing "k" elements out of the "v" vector (see Combinations#MATLAB).
Solution: <lang MATLAB>>> nchoosek(5,3)
ans =
10</lang>
If you want a vectorized function that returns multiple binomial coefficients given vector inputs, you must define that function yourself. A sample implementation is given below. This function takes either scalar or vector inputs for "n" and "v" and returns either a: scalar, vector, or matrix. Where the columns are indexed by the "k" vector and the rows indexed by the "n" vector. binomialCoeff.m: <lang MATLAB>function coefficients = binomialCoeff(n,k)
coefficients = zeros(numel(n),numel(k)); %Preallocate memory
columns = (1:numel(k)); %Preallocate row and column counters rows = (1:numel(n)); %Iterate over every row and column. The rows represent the n number, %and the columns represent the k number. If n is ever greater than k, %the nchoosek function will throw an error. So, we test to make sure %it isn't, if it is then we leave that entry in the coefficients matrix %zero. Which makes sense combinatorically. for row = rows for col = columns if k(col) <= n(row) coefficients(row,col) = nchoosek(n(row),k(col)); end end end
end %binomialCoeff</lang> Sample Usage: <lang MATLAB>>> binomialCoeff((0:5),(0:5))
ans =
1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 1 3 3 1 0 0 1 4 6 4 1 0 1 5 10 10 5 1
>> binomialCoeff([1 0 3 2],(0:3))
ans =
1 1 0 0 1 0 0 0 1 3 3 1 1 2 1 0
>> binomialCoeff(3,(0:3))
ans =
1 3 3 1
>> binomialCoeff((0:3),2)
ans =
0 0 1 3
>> binomialCoeff(5,3)
ans =
10</lang>
OCaml
<lang OCaml> let binomialCoeff n p =
let rec cm res num denum = (* this method partially prevents overflow * it also ensures an integral result *) if denum <= p then cm ((res * num) / denum) (num - 1) (denum + 1) else res in cm 1 n 1
</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>
PicoLisp
<lang PicoLisp>(de binomial (N K)
(let f '((N) (apply * (range 1 N))) (/ (f N) (* (f (- N K)) (f K))) ) )</lang>
Output:
: (binomial 5 3) -> 10
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>
R
R's built-in choose() function evaluates binomial coefficients: <lang>choose(5,3)</lang>
Output: <lang>[1] 10</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>