Evaluate binomial coefficients: Difference between revisions
m (→optimized: changed section header wording.) |
(→{{header|Perl 6}}: shortening a bit, also possibly more efficient (?)) |
||
Line 1,008: | Line 1,008: | ||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
<lang perl6>sub infix:<choose>($n, $k) { |
<lang perl6>sub infix:<choose>($n, $k) { [*] $n-$k+1 .. $n Z/ 1 .. $k } |
||
say 5 choose 3;</lang> |
say 5 choose 3;</lang> |
Revision as of 14:09, 21 June 2014
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:
See Also:
The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important Without replacement Task: Combinations Task: Permutations With replacement Task: Combinations with repetitions Task: Permutations with repetitions
ACL2
<lang Lisp>(defun fac (n)
(if (zp n) 1 (* n (fac (1- n)))))
(defun binom (n k)
(/ (fac n) (* (fac (- n k)) (fac k)))</lang>
Ada
<lang Ada> with Ada.Text_IO; use Ada.Text_IO; procedure Test_Binomial is
function Binomial (N, K : Natural) return Natural is Result : Natural := 1; M : Natural; begin if N < K then raise Constraint_Error; end if; if K > N/2 then -- Use symmetry M := N - K; else M := K; end if; for I in 1..M loop Result := Result * (N - M + I) / I; end loop; return Result; end Binomial;
begin
for N in 0..17 loop for K in 0..N loop Put (Integer'Image (Binomial (N, K))); end loop; New_Line; end loop;
end Test_Binomial; </lang> Sample output:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
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
AppleScript
<lang AppleScript>set n to 5 set k to 3
on calculateFactorial(val) set partial_factorial to 1 as integer repeat with i from 1 to val set factorial to i * partial_factorial set partial_factorial to factorial end repeat return factorial end calculateFactorial
set n_factorial to calculateFactorial(n) set k_factorial to calculateFactorial(k) set n_minus_k_factorial to calculateFactorial(n - k)
return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer </lang>
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
BBC BASIC
<lang bbcbasic> @%=&1010
PRINT "Binomial (5,3) = "; FNbinomial(5, 3) PRINT "Binomial (100,2) = "; FNbinomial(100, 2) PRINT "Binomial (33,17) = "; FNbinomial(33, 17) END DEF FNbinomial(N%, K%) LOCAL R%, D% R% = 1 : D% = N% - K% IF D% > K% THEN K% = D% : D% = N% - K% WHILE N% > K% R% *= N% N% -= 1 WHILE D% > 1 AND (R% MOD D%) = 0 R% /= D% D% -= 1 ENDWHILE ENDWHILE = R%
</lang> Output:
Binomial (5,3) = 10 Binomial (100,2) = 4950 Binomial (33,17) = 1166803110
Bracmat
<lang bracmat>(binomial=
n k coef
. !arg:(?n,?k)
& (!n+-1*!k:<!k:?k|) & 1:?coef & whl ' ( !k:>0 & !coef*!n*!k^-1:?coef & !k+-1:?k & !n+-1:?n ) & !coef
);
binomial$(5,3) 10 </lang>
Burlesque
<lang burlesque> blsq ) 5 3nr 10 </lang>
C
<lang C>#include <stdio.h>
- include <limits.h>
typedef unsigned long ULONG;
ULONG binomial(ULONG n, ULONG k) { ULONG r = 1, d = n - k;
/* choose the smaller of k and n - k */ if (d > k) { k = d; d = n - k; }
while (n > k) { if (r >= UINT_MAX / n) return 0; /* overflown */ r *= n--;
/* divide (n - k)! as soon as we can to delay overflows */ while (d > 1 && !(r % d)) r /= d--; } return r; }
int main() { printf("%lu\n", binomial(5, 3)); return 0; }</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; if(nValue2 == 1)return nValue; 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) { ulong n = 1000000, k = 3; ulong result = biCoefficient(n, k); Console.WriteLine("The Binomial Coefficient of {0}, and {1}, is equal to: {2}", n, k, result); Console.ReadLine(); }
static int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); }
static ulong biCoefficient(ulong n, ulong k) { if (k > n - k) { k = n - k; }
ulong c = 1; for (uint i = 0; i < k; i++) { c = c * (n - i); c = c / (i + 1); } return c; } }
}</lang>
Clojure
<lang clojure>(defn binomial-coefficient [n k]
(let [rprod (fn [a b] (reduce * (range a (inc b))))] (/ (rprod (- n k -1) n) (rprod 1 k))))</lang>
CoffeeScript
<lang coffeescript> binomial_coefficient = (n, k) ->
result = 1 for i in [0...k] result *= (n - i) / (i + 1) result
n = 5 for k in [0..n]
console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}"
</lang>
output <lang> > coffee binomial.coffee binomial_coefficient(5, 0) = 1 binomial_coefficient(5, 1) = 5 binomial_coefficient(5, 2) = 10 binomial_coefficient(5, 3) = 10 binomial_coefficient(5, 4) = 5 binomial_coefficient(5, 5) = 1 </lang>
Common Lisp
<lang lisp> (defun choose (n k)
(labels ((prod-enum (s e)
(do ((i s (1+ i)) (r 1 (* i r))) ((> i e) r))) (fact (n) (prod-enum 1 n)))
(/ (prod-enum (- (1+ n) k) n) (fact k))))
</lang>
D
<lang d>T binomial(T)(in T n, T k) pure nothrow {
if (k > (n / 2)) k = n - k; T bc = 1; foreach (T i; T(2) .. k + 1) bc = (bc * (n - k + i)) / i; return bc;
}
void main() {
import std.stdio, std.bigint;
foreach (const d; [[5, 3], [100, 2], [100, 98]]) writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1])); writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt));
}</lang>
- Output:
( 5 3) = 2 (100 2) = 50 (100 98) = 50 (100 50) = 1976664223067613962806675336
dc
<lang dc>[sx1q]sz[d0=zd1-lfx*]sf[skdlfxrlk-lfxlklfx*/]sb</lang>
Demonstration:
<lang dc>5 3lbxp</lang> 10
Annotated version:
<lang dc>[ macro z: factorial base case when n is (z)ero ]sx [sx [ x is our dump register; get rid of extraneous copy of n we no longer need]sx
1 [ return value is 1 ]sx q] [ abort processing of calling macro ]sx
sz
[ macro f: factorial ]sx [
d [ duplicate the input (n) ]sx 0 =z [ if n is zero, call z, which stops here and returns 1 ]sx d [ otherwise, duplicate n again ]sx 1 - [ subtract 1 ]sx lfx [ take the factorial ]sx * [ we have (n-1)!; multiply it by the copy of n to get n! ]sx
] sf
[ macro b(n,k): binomial function (n choose k).
straightforward RPN version of formula.]sx [ sk [ remember k. stack: n ]sx d [ duplicate: n n ]sx lfx [ call factorial: n n! ]sx r [ swap: n! n ]sx lk [ load k: n! n k ]sx - [ subtract: n! n-k ]sx lfx [ call factorial: n! (n-k)! ]sx lk [ load k: n! (n-k)! k ]sx lfx [ call factorial; n! (n-k)! k! ]sx * [ multiply: n! (n-k)!k! ]sx / [ divide: n!/(n-k)!k! ]sx
] sb
5 3 lb x p [print(5 choose 3)]sx</lang>
Delphi
<lang Delphi>program Binomial;
{$APPTYPE CONSOLE}
function BinomialCoff(N, K: Cardinal): Cardinal; var
L: Cardinal;
begin
if N < K then Result:= 0 // Error else begin if K > N - K then K:= N - K; // Optimization Result:= 1; L:= 0; while L < K do begin Result:= Result * (N - L); Inc(L); Result:= Result div L; end; end;
end;
begin
Writeln('C(5,3) is ', BinomialCoff(5, 3)); ReadLn;
end.</lang>
Erlang
<lang erlang> choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) ->
choose(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 choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..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>
Frink
Frink has a built-in efficient function to find binomial coefficients. It produces arbitrarily-large integers. <lang frink> println[binomial[5,3]] </lang>
FunL
FunL has pre-defined function choose
in module integers
, which is defined as:
<lang funl>def
choose( n, k ) | k < 0 or k > n = 0 choose( n, 0 ) = 1 choose( n, n ) = 1 choose( n, k ) = product( [(n - i)/(i + 1) | i <- 0:min( k, n - k )] )
println( choose(5, 3) ) println( choose(60, 30) )</lang>
- Output:
10 118264581564861424
Here it is defined using the recommended formula for this task. <lang funl>import integers.factorial
def
binomial( n, k ) | k < 0 or k > n = 0 binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )</lang>
GAP
<lang gap># Built-in Binomial(5, 3);
- 10</lang>
Go
<lang go>package main import "fmt" import "math/big"
func main() {
fmt.Println(new(big.Int).Binomial(5, 3)) fmt.Println(new(big.Int).Binomial(60, 30))
}</lang>
- Output:
10 118264581564861424
Golfscript
Actually evaluating n!/(k! (n-k)!): <lang golfscript>;5 3 # Set up demo input {),(;{*}*}:f; # Define a factorial function .f@.f@/\@-f/</lang> But Golfscript is meant for golfing, and it's shorter to calculate :
<lang golfscript>;5 3 # Set up demo input 1\,@{1$-@\*\)/}+/</lang>
Groovy
Solution: <lang groovy>def factorial = { x ->
assert x > -1 x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor }
}
def combinations = { n, k ->
assert k >= 0 assert n >= k factorial(n).intdiv(factorial(k)*factorial(n-k))
}</lang>
Test: <lang groovy>assert combinations(20, 0) == combinations(20, 20) assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10)) assert combinations(5, 3) == 10 println combinations(5, 3)</lang>
Output:
10
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>
Or, generate the binomial coefficients iteratively to avoid computing with big numbers:
<lang haskell> choose :: (Integral a) => a -> a -> a choose n k = foldl (\z i -> (z * (n-i+1)) `div` i) 1 [1..k] </lang>
HicEst
<lang HicEst>WRITE(Messagebox) BinomCoeff( 5, 3) ! displays 10
FUNCTION factorial( n )
factorial = 1 DO i = 1, n factorial = factorial * i ENDDO
END
FUNCTION BinomCoeff( n, k )
BinomCoeff = factorial(n)/factorial(n-k)/factorial(k)
END</lang>
Icon and Unicon
<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>
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 Binomial {
private static long binomial(int n, int k) { if (k>n-k) k=n-k; long b=1; for (int i=1, m=n; i<=k; i++, m--) b=b*m/i; return b; }
public static void main(String[] args) { System.out.println(binomial(5, 3)); }
}</lang> Output:
10
<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
Recursive version:
<lang java>public class Binomial {
private static long binom(int n, int k) { if (k==0) return 1; else if (k>n-k) return binom(n, n-k); else return binom(n-1, k-1)*n/k; }
public static void main(String[] args) { System.out.println(binom(5, 3)); }
}</lang> Output:
10
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
K
<lang K> {[n;k]_(*/(k-1)_1+!n)%(*/1+!k)} . 5 3 10</lang>
Alternative version: <lang K> {[n;k]i:!(k-1);_*/((n-i)%(i+1))} . 5 3 10</lang>
Using Pascal's triangle: <lang K> pascal:{x{+':0,x,0}\1}
pascal 5
(1
1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1)
{[n;k](pascal n)[n;k]} . 5 3
10</lang>
Lasso
<lang Lasso>define binomial(n::integer,k::integer) => { #k == 0 ? return 1 local(result = 1) loop(#k) => { #result = #result * (#n - loop_count + 1) / loop_count } return #result } // Tests binomial(5, 3) binomial(5, 4) binomial(60, 30)</lang>
- Output:
10 5 118264581564861424
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>
Lua
<lang lua>function Binomial( n, k )
if k > n then return nil end if k > n/2 then k = n - k end -- (n k) = (n n-k) numer, denom = 1, 1 for i = 1, k do numer = numer * ( n - i + 1 ) denom = denom * i end return numer / denom
end</lang>
Liberty BASIC
<lang lb>
' [RC] Binomial Coefficients
print "Binomial Coefficient of "; 5; " and "; 3; " is ",BinomialCoefficient( 5, 3) n =1 +int( 10 *rnd( 1)) k =1 +int( n *rnd( 1)) print "Binomial Coefficient of "; n; " and "; k; " is ",BinomialCoefficient( n, k)
end
function BinomialCoefficient( n, k) BinomialCoefficient =factorial( n) /factorial( n -k) /factorial( k) end function
function factorial( n) if n <2 then f =1 else f =n *factorial( n -1) end if factorial =f end function </lang>
Maple
<lang Maple>convert(binomial(n,k),factorial);
binomial(5,3);</lang> Output:
factorial(n) ----------------------------- factorial(k) factorial(n - k) 10
Mathematica
<lang Mathematica>(Local) In[1]:= Binomial[5,3] (Local) Out[1]= 10</lang>
MATLAB / Octave
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>
Alternative implementations are:
<lang MATLAB>function r = binomcoeff1(n,k)
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n r = r(k);
end; </lang>
<lang MATLAB>function r = binomcoeff2(n,k)
prod((n-k+1:n)./(1:k))
end; </lang>
<lang MATLAB>function r = binomcoeff3(n,k)
m = pascal(max(n-k,k)+1); r = m(n-k+1,k+1);
end; </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>
Maxima
<lang maxima>binomial( 5, 3); /* 10 */ binomial(-5, 3); /* -35 */ binomial( 5, -3); /* 0 */ binomial(-5, -3); /* 0 */ binomial( 3, 5); /* 0 */
binomial(x, 3); /* ((x - 2)*(x - 1)*x)/6 */
binomial(3, 1/2); /* binomial(3, 1/2) */ makegamma(%); /* 32/(5*%pi) */
binomial(a, b); /* binomial(a, b) */ makegamma(%); /* gamma(a + 1)/(gamma(-b + a + 1)*gamma(b + 1)) */</lang>
МК-61/52
<lang>П1 <-> П0 ПП 22 П2 ИП1 ПП 22 П3 ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3 / С/П ВП П0 1 ИП0 * L0 25 В/О</lang>
Input: n ^ k В/О С/П.
OCaml
<lang OCaml> let binomialCoeff n p =
let p = if p < n -. p then p else n -. p in let rec cm res num denum = (* this method partially prevents overflow. * float type is choosen to have increased domain on 32-bits computer, * however algorithm ensures an integral result as long as it is possible *) if denum <= p then cm ((res *. num) /. denum) (num -. 1.) (denum +. 1.) else res in cm 1. n 1.
</lang>
Alternate version using big integers
<lang ocaml>#load "nums.cma";; open Num;;
let binomial n p =
let m = min p (n - p) in if m < 0 then Int 0 else let rec a j v = if j = m then v else a (succ j) ((v */ (Int (n - j))) // (Int (succ j))) in a 0 (Int 1)
- </lang>
Simple recursive version
<lang OCaml>open Num;; let rec binomial n k = if n = k then Int 1 else ((binomial (n-1) k) */ Int n) // Int (n-k)</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>
PARI/GP
<lang parigp>binomial(5,3)</lang>
Pascal
See Delphi
Perl
<lang perl>sub binomial { use bigint; my ($r, $n, $k) = (1, @_); for (1 .. $k) { $r *= $n + 1 - $_; $r /= $_ } $r; }
print binomial(30, 13);</lang>
Perl 6
<lang perl6>sub infix:<choose>($n, $k) { [*] $n-$k+1 .. $n Z/ 1 .. $k }
say 5 choose 3;</lang>
- Output:
10
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>
PHP
<lang PHP><?php $n=5; $k=3; function factorial($val){
for($f=2;$val-1>1;$f*=$val--); return $f;
} $binomial_coefficient=factorial($n)/(factorial($k)*factorial($n-$k)); echo $binomial_coefficient; ?></lang>
Alternative version, not based on factorial <lang PHP> function binomial_coefficient($n, $k) {
if ($k == 0) return 1; $result = 1; foreach (range(0, $k - 1) as $i) { $result *= ($n - $i) / ($i + 1); } return $result;
} </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 r>choose(5,3)</lang>
Output: <lang r>[1] 10</lang>
Racket
<lang racket>
- lang racket
(require math) (binomial 10 5) </lang>
REXX
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits.
idiomatic
<lang rexx>/*REXX program calculates binomial coefficients (aka, combinations). */ numeric digits 100000 /*allow some gihugeic numbers. */ parse arg n k . /*get N and K from the C.L.*/ say 'combinations('n","k')=' comb(n,k) /*display the result to terminal.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────COMB subroutine─────────────────────*/ comb: procedure; parse arg x,y; return fact(x) % (fact(x-y) * fact(y)) /*──────────────────────────────────FACT subroutine─────────────────────*/ fact: procedure; !=1; do j=2 to arg(1); !=!*j; end; return !</lang> output when using the input of: 5 3
combinations(5,3)= 10
output when using the input of: 1200 120
combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600
optimized
This REXX version takes advantage of reducing the size (product) of the numerator,
and also, only two (factorial) products are calculated.
<lang rexx>/*REXX program calculates binomial coefficients (aka, combinations). */
numeric digits 100000 /*allow some gihugeic numbers. */
parse arg n k . /*get N and K from the C.L.*/
say 'combinations('n","k')=' comb(n,k) /*display the result to terminal.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────COMB subroutine─────────────────────*/
comb: procedure; parse arg x,y; return pfact(x-y+1,x) % pfact(2,y)
/*──────────────────────────────────PFACT subroutine────────────────────*/
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end; return !</lang>
output is identical to the 1st version.
It is (around average) about ten times faster for 200,20 and 100,10.
For 100,80 it is about 30% faster.
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
another implementation:
<lang ruby> def c n, r
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end
end </lang>
Run BASIC
<lang runbasic>print "binomial (5,1) = "; binomial(5, 1) print "binomial (5,2) = "; binomial(5, 2) print "binomial (5,3) = "; binomial(5, 3) print "binomial (5,4) = "; binomial(5,4) print "binomial (5,5) = "; binomial(5,5) end
function binomial(n,k)
coeff = 1 for i = n - k + 1 to n coeff = coeff * i next i for i = 1 to k coeff = coeff / i next i
binomial = coeff end function</lang>Output:
binomial (5,1) = 5 binomial (5,2) = 10 binomial (5,3) = 10 binomial (5,4) = 5 binomial (5,5) = 1
Scala
<lang scala>object Binomial {
def main(args: Array[String]): Unit = { val n=5 val k=3 val result=binomialCoefficient(n,k) println("The Binomial Coefficient of %d and %d equals %d.".format(n, k, result)) }
def binomialCoefficient(n:Int, k:Int)=fact(n) / (fact(k) * fact(n-k)) def fact(n:Int):Int=if (n==0) 1 else n*fact(n-1)
}</lang> Output: <lang>The Binomial Coefficient of 5 and 3 equals 10.</lang>
Another (more flexible and efficient) implementation. n and k are taken from command line. The use of BigInts allows to compute coefficients of arbitrary size:
<lang scala>object Binomial extends App {
def binomialCoefficient(n: Int, k: Int) = (BigInt(n - k + 1) to n).product / (BigInt(1) to k).product
val Array(n, k) = args.map(_.toInt) println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k)))
}</lang>
Output: <lang>java Binomial 100 30 The Binomial Coefficient of 100 and 30 equals 29,372,339,821,610,944,823,963,760.</lang>
Using recursive formula C(n,k) = C(n-1,k-1) + C(n-1,k)
:
<lang scala> def bico(n: Long, k: Long): Long = (n, k) match {
case (n, 0) => 1 case (0, k) => 0 case (n, k) => bico(n - 1, k - 1) + bico(n - 1, k) } println("bico(5,3) = " + bico(5, 3))</lang>
Output: <lang>bico(5,3) = 10</lang>
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>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func integer: binomial (in integer: n, in var integer: k) is func
result var integer: binomial is 0; local var integer: l is 0; begin if n >= k then if k > n - k then k := n - k; # Optimization end if; binomial := 1; l := 0; while l < k do binomial *:= n - l; incr(l); binomial := binomial div l; end while; end if; end func;
const proc: main is func
begin writeln("binomial coefficient of (5, 3) is " <& binomial(5, 3)); end func;</lang>
Output:
binomial coefficient of (5, 3) is 10
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
TI-89 BASIC
Builtin function.
<lang ti89b>nCr(n,k)</lang>
TXR
nCk is a built-in function, along with the one for permutations, nPk:
<lang sh>$ txr -p '(n-choose-k 20 15)' 15504</lang>
<lang sh>$ txr -p '(n-perm-k 20 15)' 20274183401472000</lang>
UNIX Shell
<lang sh>#!/bin/sh n=5; k=3; calculate_factorial(){ partial_factorial=1; for (( i=1; i<="$1"; i++ )) do
factorial=$(expr $i \* $partial_factorial) partial_factorial=$factorial
done echo $factorial }
n_factorial=$(calculate_factorial $n) k_factorial=$(calculate_factorial $k) n_minus_k_factorial=$(calculate_factorial `expr $n - $k`) binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial )
echo "Binomial Coefficient ($n,$k) = $binomial_coefficient"</lang>
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>
XPL0
<lang XPL0>code ChOut=8, CrLf=9, IntOut=11;
func Binomial(N, K); int N, K; int M, B, I; [M:= K; if K>N/2 the M:= N-K; B:=1; for I:= 1 to M do
B:= B*(N-M+I)/I;
return B; ];
int N, K; [for N:= 0 to 9 do
[for K:= 0 to 9 do [if N>=K then IntOut(0, Binomial(N,K)); ChOut(0, 9\tab\); ]; CrLf(0); ];
] \Mr. Pascal's triangle!</lang>
Output:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
zkl
Using 64 bit ints: <lang zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }</lang>
- Output:
zkl: binomial(5,3) 10 zkl: binomial(60,30) 118264581564861424
- Programming Tasks
- Mathematical operations
- ACL2
- Ada
- ALGOL 68
- AppleScript
- AutoHotkey
- BBC BASIC
- Bracmat
- Burlesque
- C
- C++
- C sharp
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dc
- Delphi
- Erlang
- F Sharp
- Forth
- Fortran
- Frink
- FunL
- GAP
- Go
- Golfscript
- Groovy
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- K
- Lasso
- Logo
- Lua
- Liberty BASIC
- Maple
- Mathematica
- MATLAB
- Octave
- Maxima
- МК-61/52
- OCaml
- Oz
- PARI/GP
- Pascal
- Perl
- Perl 6
- PL/I
- PHP
- PicoLisp
- PureBasic
- Python
- R
- Racket
- REXX
- Ruby
- Run BASIC
- Scala
- Scheme
- Seed7
- Tcl
- TI-89 BASIC
- TXR
- UNIX Shell
- Ursala
- XPL0
- Zkl