Evaluate binomial coefficients: Difference between revisions
Alter JavaScript version, fixing a rounding bug that occurred with inputs `binom(50, 25)` and `binom(100, 10)` |
|||
(49 intermediate revisions by 29 users not shown) | |||
Line 15: | Line 15: | ||
{{Template:Combinations and permutations}} |
{{Template:Combinations and permutations}} |
||
<br> |
<br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F binomial_coeff(n, k) |
|||
V result = 1 |
|||
L(i) 1..k |
|||
result = result * (n - i + 1) / i |
|||
R result |
|||
print(binomial_coeff(5, 3))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10 |
|||
</pre> |
|||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
{{trans|ABAP}} |
{{trans|ABAP}} |
||
Very compact version. |
Very compact version. |
||
< |
<syntaxhighlight lang="360asm">* Evaluate binomial coefficients - 29/09/2015 |
||
BINOMIAL CSECT |
BINOMIAL CSECT |
||
USING BINOMIAL,R15 set base register |
USING BINOMIAL,R15 set base register |
||
Line 42: | Line 57: | ||
PG DS CL12 buffer |
PG DS CL12 buffer |
||
YREGS |
YREGS |
||
END BINOMIAL</ |
END BINOMIAL</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 49: | Line 64: | ||
=={{header|ABAP}}== |
=={{header|ABAP}}== |
||
< |
<syntaxhighlight lang="abap">CLASS lcl_binom DEFINITION CREATE PUBLIC. |
||
PUBLIC SECTION. |
PUBLIC SECTION. |
||
Line 76: | Line 91: | ||
ENDMETHOD. |
ENDMETHOD. |
||
ENDCLASS.</ |
ENDCLASS.</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>lcl_binom=>calc( n = 5 k = 3 ) |
<pre>lcl_binom=>calc( n = 5 k = 3 ) |
||
Line 85: | Line 100: | ||
=={{header|ACL2}}== |
=={{header|ACL2}}== |
||
< |
<syntaxhighlight lang="lisp">(defun fac (n) |
||
(if (zp n) |
(if (zp n) |
||
1 |
1 |
||
Line 91: | Line 106: | ||
(defun binom (n k) |
(defun binom (n k) |
||
(/ (fac n) (* (fac (- n k)) (fac k)))</ |
(/ (fac n) (* (fac (- n k)) (fac k)))</syntaxhighlight> |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang="ada"> |
|||
<lang Ada> |
|||
with Ada.Text_IO; use Ada.Text_IO; |
with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Test_Binomial is |
procedure Test_Binomial is |
||
Line 122: | Line 137: | ||
end loop; |
end loop; |
||
end Test_Binomial; |
end Test_Binomial; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 155: | Line 170: | ||
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}} |
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}} |
||
< |
<syntaxhighlight lang="algol68">PROC factorial = (INT n)INT: |
||
( |
( |
||
INT result; |
INT result; |
||
Line 179: | Line 194: | ||
test:( |
test:( |
||
print((choose(5, 3), new line)) |
print((choose(5, 3), new line)) |
||
)</ |
)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 186: | Line 201: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% calculates n!/k! % |
% calculates n!/k! % |
||
integer procedure factorialOverFactorial( integer value n, k ) ; |
integer procedure factorialOverFactorial( integer value n, k ) ; |
||
Line 217: | Line 232: | ||
write( binomialCoefficient( 5, 3 ) ) |
write( binomialCoefficient( 5, 3 ) ) |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|APL}}== |
|||
When the factorial operator <tt>!</tt> is used as a dyad, it returns the binomial coefficient: <tt>k!n</tt> = <i>n</i> choose <i>k</i>. |
|||
<syntaxhighlight lang="apl"> 3!5 |
|||
10</syntaxhighlight> |
|||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
===Imperative=== |
===Imperative=== |
||
< |
<syntaxhighlight lang="applescript">set n to 5 |
||
set k to 3 |
set k to 3 |
||
Line 238: | Line 258: | ||
return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer |
return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Functional=== |
===Functional=== |
||
Line 244: | Line 264: | ||
Using a little more abstraction for readability, and currying for ease of both re-use and refactoring: |
Using a little more abstraction for readability, and currying for ease of both re-use and refactoring: |
||
< |
<syntaxhighlight lang="applescript">-- factorial :: Int -> Int |
||
on factorial(n) |
on factorial(n) |
||
product(enumFromTo(1, n)) |
product(enumFromTo(1, n)) |
||
Line 321: | Line 341: | ||
foldl(multiply, 1, xs) |
foldl(multiply, 1, xs) |
||
end product</ |
end product</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{10, 10}</pre> |
<pre>{10, 10}</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">factorial: function [n]-> product 1..n |
|||
binomial: function [x,y]-> (factorial x) / (factorial y) * factorial x-y |
|||
print binomial 5 3</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox, % Round(BinomialCoefficient(5, 3)) |
||
;--------------------------------------------------------------------------- |
;--------------------------------------------------------------------------- |
||
Line 337: | Line 368: | ||
} |
} |
||
Return, r |
Return, r |
||
}</ |
}</syntaxhighlight> |
||
Message box shows: |
Message box shows: |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f EVALUATE_BINOMIAL_COEFFICIENTS.AWK |
# syntax: GAWK -f EVALUATE_BINOMIAL_COEFFICIENTS.AWK |
||
BEGIN { |
BEGIN { |
||
Line 356: | Line 388: | ||
printf("%d %d = %d\n",n,k,r) |
printf("%d %d = %d\n",n,k,r) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 365: | Line 397: | ||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
< |
<syntaxhighlight lang="dos">@echo off & setlocal |
||
if "%~2"=="" ( echo Usage: %~nx0 n k && goto :EOF ) |
if "%~2"=="" ( echo Usage: %~nx0 n k && goto :EOF ) |
||
Line 381: | Line 413: | ||
for /L %%I in (1, 1, %~3) do set /a coeff /= %%I |
for /L %%I in (1, 1, %~3) do set /a coeff /= %%I |
||
endlocal && set "%~1=%coeff%" |
endlocal && set "%~1=%coeff%" |
||
goto :EOF</ |
goto :EOF</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 404: | Line 436: | ||
</pre> |
</pre> |
||
The Windows cmd console only handles 32-bit integers. If a factoral exceeds 2147483647 at any point, <code>set /a</code> will choke and roll over to a negative value, giving unexpected results. Unfortunately, this is as good as it gets for pure batch. |
The Windows cmd console only handles 32-bit integers. If a factoral exceeds 2147483647 at any point, <code>set /a</code> will choke and roll over to a negative value, giving unexpected results. Unfortunately, this is as good as it gets for pure batch. |
||
=={{header|BCPL}}== |
|||
<syntaxhighlight lang="bcpl"> |
|||
GET "libhdr" |
|||
LET choose(n, k) = |
|||
~(0 <= k <= n) -> 0, |
|||
2*k > n -> binomial(n, n - k), |
|||
binomial(n, k) |
|||
AND binomial(n, k) = |
|||
k = 0 -> 1, |
|||
binomial(n, k - 1) * (n - k + 1) / k |
|||
LET start() = VALOF { |
|||
LET n, k = ?, ? |
|||
LET argv = VEC 20 |
|||
LET sz = ? |
|||
sz := rdargs("n/a/n/p,k/a/n/p", argv, 20) |
|||
UNLESS sz ~= 0 RESULTIS 1 |
|||
n := !argv!0 |
|||
k := !argv!1 |
|||
writef("%d choose %d = %d *n", n, k, choose(n, k)) |
|||
RESULTIS 0 |
|||
} |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
Note that with the /p flag to rdargs(), the system will prompt if we don't supply both arguments on the command line. |
|||
<pre> |
|||
$ cintsys64 |
|||
BCPL 64-bit Cintcode System (13 Jan 2020) |
|||
0.004> nCk 50 25 |
|||
50 choose 25 = 126410606437752 |
|||
0.003> nCk 10 5 |
|||
10 choose 5 = 252 |
|||
0.004> nCk 100 2 |
|||
100 choose 2 = 4950 |
|||
0.000> nCk 100 98 |
|||
100 choose 98 = 4950 |
|||
0.004> nCk |
|||
n > 5 |
|||
k > 3 |
|||
5 choose 3 = 10 |
|||
</pre> |
|||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
< |
<syntaxhighlight lang="bbcbasic"> @%=&1010 |
||
PRINT "Binomial (5,3) = "; FNbinomial(5, 3) |
PRINT "Binomial (5,3) = "; FNbinomial(5, 3) |
||
Line 426: | Line 506: | ||
ENDWHILE |
ENDWHILE |
||
= R% |
= R% |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>Binomial (5,3) = 10 |
<pre>Binomial (5,3) = 10 |
||
Line 433: | Line 513: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang="bracmat">(binomial= |
||
n k coef |
n k coef |
||
. !arg:(?n,?k) |
. !arg:(?n,?k) |
||
Line 449: | Line 529: | ||
binomial$(5,3) |
binomial$(5,3) |
||
10 |
10 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Burlesque}}== |
=={{header|Burlesque}}== |
||
< |
<syntaxhighlight lang="burlesque"> |
||
blsq ) 5 3nr |
blsq ) 5 3nr |
||
10 |
10 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <limits.h> |
#include <limits.h> |
||
Line 501: | Line 581: | ||
printf("%lu\n", binomial(67, 31)); |
printf("%lu\n", binomial(67, 31)); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>10 |
<pre>10 |
||
131282408400 |
131282408400 |
||
11923179284862717872</pre> |
11923179284862717872</pre> |
||
=={{header|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 binomialCoefficient(double n, double k) |
|||
{ |
|||
if (abs(n - k) < 1e-7 || k < 1e-7) return 1.0; |
|||
if( abs(k-1.0) < 1e-7 || abs(k - (n-1)) < 1e-7)return n; |
|||
return Factorial(n) /(Factorial(k)*Factorial((n - k))); |
|||
} |
|||
</lang> |
|||
Implementation: |
|||
<lang cpp>int main() |
|||
{ |
|||
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< binomialCoefficient(5,3); |
|||
cin.get(); |
|||
}</lang> |
|||
{{Out}} |
|||
<pre>The Binomial Coefficient of 5, and 3, is equal to: 10</pre> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
namespace BinomialCoefficients |
namespace BinomialCoefficients |
||
Line 578: | Line 624: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
|||
<syntaxhighlight 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 binomialCoefficient(double n, double k) |
|||
{ |
|||
if (abs(n - k) < 1e-7 || k < 1e-7) return 1.0; |
|||
if( abs(k-1.0) < 1e-7 || abs(k - (n-1)) < 1e-7)return n; |
|||
return Factorial(n) /(Factorial(k)*Factorial((n - k))); |
|||
} |
|||
</syntaxhighlight> |
|||
Implementation: |
|||
<syntaxhighlight lang="cpp">int main() |
|||
{ |
|||
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< binomialCoefficient(5,3); |
|||
cin.get(); |
|||
}</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>The Binomial Coefficient of 5, and 3, is equal to: 10</pre> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(defn binomial-coefficient [n k] |
||
(let [rprod (fn [a b] (reduce * (range a (inc b))))] |
(let [rprod (fn [a b] (reduce * (range a (inc b))))] |
||
(/ (rprod (- n k -1) n) (rprod 1 k))))</ |
(/ (rprod (- n k -1) n) (rprod 1 k))))</syntaxhighlight> |
||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
binomial_coefficient = (n, k) -> |
binomial_coefficient = (n, k) -> |
||
result = 1 |
result = 1 |
||
Line 596: | Line 676: | ||
for k in [0..n] |
for k in [0..n] |
||
console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}" |
console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}}<pre> |
{{Out}}<pre> |
||
Line 607: | Line 687: | ||
binomial_coefficient(5, 5) = 1 |
binomial_coefficient(5, 5) = 1 |
||
</pre> |
</pre> |
||
=={{header|Commodore BASIC}}== |
|||
<syntaxhighlight lang="freebasic"> |
|||
10 REM BINOMIAL COEFFICIENTS |
|||
20 REM COMMODORE BASIC 2.0 |
|||
30 REM 2021-08-24 |
|||
40 REM BY ALVALONGO |
|||
100 Z=0:U=1 |
|||
110 FOR N=U TO 10 |
|||
120 PRINT N; |
|||
130 FOR K=Z TO N |
|||
140 GOSUB 900 |
|||
150 PRINT C; |
|||
160 NEXT K |
|||
170 PRINT |
|||
180 NEXT N |
|||
190 END |
|||
900 REM BINOMIAL COEFFICIENT |
|||
910 IF K<Z OR K>N THEN C=Z:RETURN |
|||
920 IF K=Z OR K=N THEN C=U:RETURN |
|||
930 P=K:IF N-K<P THEN P=N-K |
|||
940 C=U |
|||
950 FOR I=Z TO P-U |
|||
960 C=C/(I+U)*(N-I) |
|||
980 NEXT I |
|||
990 RETURN |
|||
</syntaxhighlight> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun choose (n k) |
(defun choose (n k) |
||
(labels ((prod-enum (s e) |
(labels ((prod-enum (s e) |
||
Line 615: | Line 731: | ||
(fact (n) (prod-enum 1 n))) |
(fact (n) (prod-enum 1 n))) |
||
(/ (prod-enum (- (1+ n) k) n) (fact k)))) |
(/ (prod-enum (- (1+ n) k) n) (fact k)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">T binomial(T)(in T n, T k) pure nothrow { |
||
if (k > (n / 2)) |
if (k > (n / 2)) |
||
k = n - k; |
k = n - k; |
||
Line 633: | Line 749: | ||
writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1])); |
writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1])); |
||
writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt)); |
writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>( 5 3) = 2 |
<pre>( 5 3) = 2 |
||
Line 640: | Line 756: | ||
(100 50) = 1976664223067613962806675336</pre> |
(100 50) = 1976664223067613962806675336</pre> |
||
The above wouldn't work for me (100C50 correctly gives 100891344545564193334812497256). |
The above wouldn't work for me (100C50 correctly gives 100891344545564193334812497256). |
||
<lang d>T BinomialCoeff(T)(in T n, in T k) |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="d">T BinomialCoeff(T)(in T n, in T k) |
|||
{ |
{ |
||
T nn = n, kk = k, c = cast(T)1; |
T nn = n, kk = k, c = cast(T)1; |
||
Line 662: | Line 781: | ||
BinomialCoeff(10UL, 3UL).writeln; |
BinomialCoeff(10UL, 3UL).writeln; |
||
BinomialCoeff(100.BigInt, 50.BigInt).writeln; |
BinomialCoeff(100.BigInt, 50.BigInt).writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>120 |
<pre>120 |
||
Line 668: | Line 787: | ||
=={{header|dc}}== |
=={{header|dc}}== |
||
< |
<syntaxhighlight lang="dc">[sx1q]sz[d0=zd1-lfx*]sf[skdlfxrlk-lfxlklfx*/]sb</syntaxhighlight> |
||
Demonstration: |
Demonstration: |
||
<lang |
<syntaxhighlight lang="dc">5 3lbxp</syntaxhighlight> |
||
<tt>10</tt> |
<tt>10</tt> |
||
Annotated version: |
Annotated version: |
||
< |
<syntaxhighlight 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 |
[sx [ x is our dump register; get rid of extraneous copy of n we no longer need]sx |
||
1 [ return value is 1 ]sx |
1 [ return value is 1 ]sx |
||
Line 707: | Line 826: | ||
] sb |
] sb |
||
5 3 lb x p [print(5 choose 3)]sx</ |
5 3 lb x p [print(5 choose 3)]sx</syntaxhighlight> |
||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
< |
<syntaxhighlight lang="delphi">program Binomial; |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 738: | Line 857: | ||
Writeln('C(5,3) is ', BinomialCoff(5, 3)); |
Writeln('C(5,3) is ', BinomialCoff(5, 3)); |
||
ReadLn; |
ReadLn; |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang=text> |
|||
func binomial n k . |
|||
if k > n / 2 |
|||
k = n - k |
|||
. |
|||
numer = 1 |
|||
for i = n downto n - k + 1 |
|||
numer = numer * i |
|||
. |
|||
denom = 1 |
|||
for i = 1 to k |
|||
denom = denom * i |
|||
. |
|||
return numer / denom |
|||
. |
|||
print binomial 5 3 |
|||
</syntaxhighlight> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def choose(n,k) when is_integer(n) and is_integer(k) and n>=0 and k>=0 and n>=k do |
def choose(n,k) when is_integer(n) and is_integer(k) and n>=0 and k>=0 and n>=k do |
||
if k==0, do: 1, else: choose(n,k,1,1) |
if k==0, do: 1, else: choose(n,k,1,1) |
||
Line 752: | Line 890: | ||
IO.inspect RC.choose(5,3) |
IO.inspect RC.choose(5,3) |
||
IO.inspect RC.choose(60,30)</ |
IO.inspect RC.choose(60,30)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 761: | Line 899: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang"> |
||
choose(N, 0) -> 1; |
choose(N, 0) -> 1; |
||
choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) -> |
choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) -> |
||
Line 770: | Line 908: | ||
choose(N, K, I, Acc) -> |
choose(N, K, I, Acc) -> |
||
choose(N, K, I+1, (Acc * (N-I+1)) div I). |
choose(N, K, I+1, (Acc * (N-I+1)) div I). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<lang>PROGRAM BINOMIAL |
<syntaxhighlight lang="text">PROGRAM BINOMIAL |
||
!$DOUBLE |
!$DOUBLE |
||
Line 800: | Line 938: | ||
PRINT("Binomial (33,17) = ";BIN) |
PRINT("Binomial (33,17) = ";BIN) |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Binomial (5,3) = 10 |
<pre>Binomial (5,3) = 10 |
||
Line 806: | Line 944: | ||
Binomial (33,17) = 1166803110 |
Binomial (33,17) = 1166803110 |
||
</pre> |
</pre> |
||
=={{header|F Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k] |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor"> |
||
: fact ( n -- n-factorial ) |
: fact ( n -- n-factorial ) |
||
dup 0 = [ drop 1 ] [ dup 1 - fact * ] if ; |
dup 0 = [ drop 1 ] [ dup 1 - fact * ] if ; |
||
Line 824: | Line 967: | ||
: choose-fold ( n k -- n-choose-k ) |
: choose-fold ( n k -- n-choose-k ) |
||
2dup 1 + [a,b] product -rot - 1 [a,b] product / ; |
2dup 1 + [a,b] product -rot - 1 [a,b] product / ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header| |
=={{header|Fermat}}== |
||
The binomial function is built in. |
|||
<lang fsharp> |
|||
<syntaxhighlight lang="fermat">Bin(5,3)</syntaxhighlight> |
|||
let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k] |
|||
{{out}}<pre>10</pre> |
|||
</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang="forth">: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ; |
||
5 3 choose . \ 10 |
5 3 choose . \ 10 |
||
33 17 choose . \ 1166803110</ |
33 17 choose . \ 1166803110</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
=== Direct Method === |
|||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
< |
<syntaxhighlight lang="fortran">program test_choose |
||
implicit none |
implicit none |
||
Line 869: | Line 1,014: | ||
end function choose |
end function choose |
||
end program test_choose</ |
end program test_choose</syntaxhighlight> |
||
{{Out}}<pre>10</pre> |
{{Out}}<pre>10</pre> |
||
=== Avoiding Overflow === |
|||
Of course this method doesn't avoid overflow completely just delays it. It could be extended by adding more entries to the '''primes''' array |
|||
<syntaxhighlight lang="fortran"> |
|||
program binomial |
|||
integer :: i, j |
|||
do j=1,20 |
|||
write(*,fmt='(i2,a)',advance='no') j,'Cr = ' |
|||
do i=0,j |
|||
write(*,fmt='(i0,a)',advance='no') n_C_r(j,i),' ' |
|||
end do |
|||
write(*,'(a,i0)') ' 60C30 = ',n_C_r(60,30) |
|||
end do |
|||
stop |
|||
contains |
|||
pure function n_C_r(n, r) result(bin) |
|||
integer(16) :: bin |
|||
integer, intent(in) :: n |
|||
integer, intent(in) :: r |
|||
integer(16) :: num |
|||
integer(16) :: den |
|||
integer :: i |
|||
integer :: k |
|||
integer, parameter :: primes(*) = [2,3,5,7,11,13,17,19] |
|||
num = 1 |
|||
den = 1 |
|||
do i=0,r-1 |
|||
num = num*(n-i) |
|||
den = den*(i+1) |
|||
if (i > 0) then |
|||
! Divide out common prime factors |
|||
do k=1,size(primes) |
|||
if (mod(i,primes(k)) == 0) then |
|||
num = num/primes(k) |
|||
den = den/primes(k) |
|||
end if |
|||
end do |
|||
end if |
|||
end do |
|||
bin = num/den |
|||
end function n_C_r |
|||
end program binomial |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
1Cr = 1 1 |
|||
2Cr = 1 2 1 |
|||
3Cr = 1 3 3 1 |
|||
4Cr = 1 4 6 4 1 |
|||
5Cr = 1 5 10 10 5 1 |
|||
6Cr = 1 6 15 20 15 6 1 |
|||
7Cr = 1 7 21 35 35 21 7 1 |
|||
8Cr = 1 8 28 56 70 56 28 8 1 |
|||
9Cr = 1 9 36 84 126 126 84 36 9 1 |
|||
10Cr = 1 10 45 120 210 252 210 120 45 10 1 |
|||
11Cr = 1 11 55 165 330 462 462 330 165 55 11 1 |
|||
12Cr = 1 12 66 220 495 792 924 792 495 220 66 12 1 |
|||
13Cr = 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 |
|||
14Cr = 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 |
|||
15Cr = 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 |
|||
16Cr = 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 |
|||
17Cr = 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 |
|||
18Cr = 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 |
|||
19Cr = 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 |
|||
20Cr = 1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1 |
|||
21Cr = 1 21 210 1330 5985 20349 54264 116280 203490 293930 352716 352716 293930 203490 116280 54264 20349 5985 1330 210 21 1 |
|||
22Cr = 1 22 231 1540 7315 26334 74613 170544 319770 497420 646646 705432 646646 497420 319770 170544 74613 26334 7315 1540 231 22 1 |
|||
23Cr = 1 23 253 1771 8855 33649 100947 245157 490314 817190 1144066 1352078 1352078 1144066 817190 490314 245157 100947 33649 8855 1771 253 23 1 |
|||
24Cr = 1 24 276 2024 10626 42504 134596 346104 735471 1307504 1961256 2496144 2704156 2496144 1961256 1307504 735471 346104 134596 42504 10626 2024 276 24 1 |
|||
25Cr = 1 25 300 2300 12650 53130 177100 480700 1081575 2042975 3268760 4457400 5200300 5200300 4457400 3268760 2042975 1081575 480700 177100 53130 12650 2300 300 25 1 |
|||
60C30 = 118264581564861424 |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
Function factorial(n As Integer) As Integer |
Function factorial(n As Integer) As Integer |
||
Line 903: | Line 1,124: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 927: | Line 1,148: | ||
Frink has a built-in efficient function to find binomial coefficients. |
Frink has a built-in efficient function to find binomial coefficients. |
||
It produces arbitrarily-large integers. |
It produces arbitrarily-large integers. |
||
< |
<syntaxhighlight lang="frink"> |
||
println[binomial[5,3]] |
println[binomial[5,3]] |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
FunL has pre-defined function <code>choose</code> in module <code>integers</code>, which is defined as: |
FunL has pre-defined function <code>choose</code> in module <code>integers</code>, which is defined as: |
||
< |
<syntaxhighlight lang="funl">def |
||
choose( n, k ) | k < 0 or k > n = 0 |
choose( n, k ) | k < 0 or k > n = 0 |
||
choose( n, 0 ) = 1 |
choose( n, 0 ) = 1 |
||
Line 940: | Line 1,161: | ||
println( choose(5, 3) ) |
println( choose(5, 3) ) |
||
println( choose(60, 30) )</ |
println( choose(60, 30) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 948: | Line 1,169: | ||
Here it is defined using the recommended formula for this task. |
Here it is defined using the recommended formula for this task. |
||
< |
<syntaxhighlight lang="funl">import integers.factorial |
||
def |
def |
||
binomial( n, k ) | k < 0 or k > n = 0 |
binomial( n, k ) | k < 0 or k > n = 0 |
||
binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )</ |
binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )</syntaxhighlight> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap"># Built-in |
||
Binomial(5, 3); |
Binomial(5, 3); |
||
# 10</ |
# 10</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
import "math/big" |
import "math/big" |
||
Line 967: | Line 1,188: | ||
fmt.Println(new(big.Int).Binomial(5, 3)) |
fmt.Println(new(big.Int).Binomial(5, 3)) |
||
fmt.Println(new(big.Int).Binomial(60, 30)) |
fmt.Println(new(big.Int).Binomial(60, 30)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 976: | Line 1,197: | ||
=={{header|Golfscript}}== |
=={{header|Golfscript}}== |
||
Actually evaluating n!/(k! (n-k)!): |
Actually evaluating n!/(k! (n-k)!): |
||
< |
<syntaxhighlight lang="golfscript">;5 3 # Set up demo input |
||
{),(;{*}*}:f; # Define a factorial function |
{),(;{*}*}:f; # Define a factorial function |
||
.f@.f@/\@-f/</ |
.f@.f@/\@-f/</syntaxhighlight> |
||
But Golfscript is meant for golfing, and it's shorter to calculate <math>\prod_{i=0}^{k-1} \frac{n-i}{i+1}</math>: |
But Golfscript is meant for golfing, and it's shorter to calculate <math>\prod_{i=0}^{k-1} \frac{n-i}{i+1}</math>: |
||
< |
<syntaxhighlight lang="golfscript">;5 3 # Set up demo input |
||
1\,@{1$-@\*\)/}+/</ |
1\,@{1$-@\*\)/}+/</syntaxhighlight> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">def factorial = { x -> |
||
assert x > -1 |
assert x > -1 |
||
x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor } |
x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor } |
||
Line 995: | Line 1,216: | ||
assert n >= k |
assert n >= k |
||
factorial(n).intdiv(factorial(k)*factorial(n-k)) |
factorial(n).intdiv(factorial(k)*factorial(n-k)) |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">assert combinations(20, 0) == combinations(20, 20) |
||
assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10)) |
assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10)) |
||
assert combinations(5, 3) == 10 |
assert combinations(5, 3) == 10 |
||
println combinations(5, 3)</ |
println combinations(5, 3)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|GW-BASIC}}== |
|||
<syntaxhighlight lang="gwbasic">10 REM BINOMIAL CALCULATOR |
|||
20 INPUT "N? ", N |
|||
30 INPUT "P? ", P |
|||
40 GOSUB 70 |
|||
50 PRINT C |
|||
60 END |
|||
70 C = 0 |
|||
80 IF N < 0 OR P<0 OR P > N THEN RETURN |
|||
90 IF P < N\2 THEN P = N - P |
|||
100 C = 1 |
|||
110 FOR I = N TO P+1 STEP -1 |
|||
120 C=C*I |
|||
130 NEXT I |
|||
140 FOR I = 1 TO N-P |
|||
150 C=C/I |
|||
160 NEXT I |
|||
170 RETURN</syntaxhighlight> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
The only trick here is realizing that everything's going to divide nicely, so we can use div instead of (/). |
The only trick here is realizing that everything's going to divide nicely, so we can use div instead of (/). |
||
< |
<syntaxhighlight lang="haskell"> |
||
choose :: (Integral a) => a -> a -> a |
choose :: (Integral a) => a -> a -> a |
||
choose n k = product [k+1..n] `div` product [1..n-k] |
choose n k = product [k+1..n] `div` product [1..n-k] |
||
</syntaxhighlight> |
|||
</lang> |
|||
< |
<syntaxhighlight lang="haskell">> 5 `choose` 3 |
||
10</ |
10</syntaxhighlight> |
||
Or, generate the binomial coefficients iteratively to avoid computing with big numbers: |
Or, generate the binomial coefficients iteratively to avoid computing with big numbers: |
||
< |
<syntaxhighlight lang="haskell"> |
||
choose :: (Integral a) => a -> a -> a |
choose :: (Integral a) => a -> a -> a |
||
choose n k = foldl (\z i -> (z * (n-i+1)) `div` i) 1 [1..k] |
choose n k = foldl (\z i -> (z * (n-i+1)) `div` i) 1 [1..k] |
||
</syntaxhighlight> |
|||
</lang> |
|||
Or using "caching": |
Or using "caching": |
||
< |
<syntaxhighlight lang="haskell">coeffs = iterate next [1] |
||
where |
where |
||
next ns = zipWith (+) (0:ns) $ ns ++ [0] |
next ns = zipWith (+) (0:ns) $ ns ++ [0] |
||
main = print $ coeffs !! 5 !! 3</ |
main = print $ coeffs !! 5 !! 3</syntaxhighlight> |
||
=={{header|HicEst}}== |
=={{header|HicEst}}== |
||
< |
<syntaxhighlight lang="hicest">WRITE(Messagebox) BinomCoeff( 5, 3) ! displays 10 |
||
FUNCTION factorial( n ) |
FUNCTION factorial( n ) |
||
Line 1,044: | Line 1,284: | ||
FUNCTION BinomCoeff( n, k ) |
FUNCTION BinomCoeff( n, k ) |
||
BinomCoeff = factorial(n)/factorial(n-k)/factorial(k) |
BinomCoeff = factorial(n)/factorial(n-k)/factorial(k) |
||
END</ |
END</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<syntaxhighlight lang="icon">link math, factors |
||
procedure main() |
procedure main() |
||
write("choose(5,3)=",binocoef(5,3)) |
write("choose(5,3)=",binocoef(5,3)) |
||
end</ |
end</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>choose(5,3)=10</pre> |
<pre>choose(5,3)=10</pre> |
||
Line 1,059: | Line 1,299: | ||
[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors provides factorial]. |
[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors provides factorial]. |
||
< |
<syntaxhighlight lang="icon">procedure binocoef(n, k) #: binomial coefficient |
||
k := integer(k) | fail |
k := integer(k) | fail |
||
Line 1,085: | Line 1,325: | ||
return i |
return i |
||
end</ |
end</syntaxhighlight> |
||
=={{header|IS-BASIC}}== |
=={{header|IS-BASIC}}== |
||
< |
<syntaxhighlight lang="is-basic">100 PROGRAM "Binomial.bas" |
||
110 PRINT "Binomial (5,3) =";BINOMIAL(5,3) |
110 PRINT "Binomial (5,3) =";BINOMIAL(5,3) |
||
120 DEF BINOMIAL(N,K) |
120 DEF BINOMIAL(N,K) |
||
Line 1,100: | Line 1,340: | ||
200 LOOP |
200 LOOP |
||
210 LET BINOMIAL=R |
210 LET BINOMIAL=R |
||
220 END DEF</ |
220 END DEF</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
Line 1,107: | Line 1,347: | ||
'''Example usage:''' |
'''Example usage:''' |
||
< |
<syntaxhighlight lang="j"> 3 ! 5 |
||
10</ |
10</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class Binomial { |
||
{ |
|||
// precise, but may overflow and then produce completely incorrect results |
|||
private static long binomial(int n, int k) |
|||
private static long binomialInt(int n, int k) { |
|||
{ |
|||
if (k>n-k) |
if (k > n - k) |
||
k=n-k; |
k = n - k; |
||
long |
long binom = 1; |
||
for (int i |
for (int i = 1; i <= k; i++) |
||
binom = binom * (n + 1 - i) / i; |
|||
return |
return binom; |
||
} |
} |
||
// same as above, but with overflow check |
|||
public static void main(String[] args) |
|||
private static Object binomialIntReliable(int n, int k) { |
|||
{ |
|||
if (k > n - k) |
|||
k = n - k; |
|||
long binom = 1; |
|||
for (int i = 1; i <= k; i++) { |
|||
try { |
|||
binom = Math.multiplyExact(binom, n + 1 - i) / i; |
|||
} catch (ArithmeticException e) { |
|||
return "overflow"; |
|||
} |
|||
} |
|||
return binom; |
|||
} |
} |
||
}</lang> |
|||
{{Out}} |
|||
<pre>10</pre> |
|||
// using floating point arithmetic, larger numbers can be calculated, |
|||
{{trans|Python}} |
|||
// but with reduced precision |
|||
<lang java>public class Binom { |
|||
private static double binomialFloat(int n, int k) { |
|||
if (k > n - k) |
|||
k = n - k; |
|||
result *= (n - i + 1) / i; |
|||
double binom = 1.0; |
|||
for (int i = 1; i <= k; i++) |
|||
binom = binom * (n + 1 - i) / i; |
|||
return binom; |
|||
} |
|||
// slow, hard to read, but precise |
|||
private static BigInteger binomialBigInt(int n, int k) { |
|||
if (k > n - k) |
|||
k = n - k; |
|||
BigInteger binom = BigInteger.ONE; |
|||
for (int i = 1; i <= k; i++) { |
|||
binom = binom.multiply(BigInteger.valueOf(n + 1 - i)); |
|||
binom = binom.divide(BigInteger.valueOf(i)); |
|||
} |
} |
||
return |
return binom; |
||
} |
|||
private static void demo(int n, int k) { |
|||
List<Object> data = Arrays.asList( |
|||
n, |
|||
k, |
|||
binomialInt(n, k), |
|||
binomialIntReliable(n, k), |
|||
binomialFloat(n, k), |
|||
binomialBigInt(n, k)); |
|||
System.out.println(data.stream().map(Object::toString).collect(Collectors.joining("\t"))); |
|||
} |
} |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
demo(5, 3); |
|||
demo(1000, 300); |
|||
} |
} |
||
}</syntaxhighlight> |
|||
} |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>10.0 |
<pre>5 3 10 10 10.0 10 |
||
1000 300 -8357011479171942 overflow 5.428250046406143E263 542825004640614064815358503892902599588060075560435179852301016412253602009800031872232761420804306539976220810204913677796961128392686442868524741815732892024613137013599170443939815681313827516308854820419235457578544489551749630302863689773725905288736148678480</pre> |
|||
Recursive version: |
Recursive version, without overflow check: |
||
< |
<syntaxhighlight lang="java">public class Binomial |
||
{ |
{ |
||
private static long binom(int n, int k) |
private static long binom(int n, int k) |
||
Line 1,168: | Line 1,444: | ||
System.out.println(binom(5, 3)); |
System.out.println(binom(5, 3)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">function binom(n, k) { |
||
var coeff = 1; |
var coeff = 1; |
||
var i; |
var i; |
||
Line 1,186: | Line 1,462: | ||
} |
} |
||
console.log(binom(5, 3)); |
console.log(binom(5, 3));</syntaxhighlight> |
||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
< |
<syntaxhighlight lang="jq"># nCk assuming n >= k |
||
def binomial(n; k): |
def binomial(n; k): |
||
if k > n / 2 then binomial(n; n-k) |
if k > n / 2 then binomial(n; n-k) |
||
Line 1,204: | Line 1,479: | ||
([5,3], [100,2], [ 33,17]) | task |
([5,3], [100,2], [ 33,17]) | task |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
5 C 3 = 10 |
5 C 3 = 10 |
||
Line 1,211: | Line 1,486: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia| |
{{works with|Julia|1.2}} |
||
'''Built-in''' |
'''Built-in''' |
||
<lang |
<syntaxhighlight lang="julia">@show binomial(5, 3)</syntaxhighlight> |
||
'''Recursive version''': |
'''Recursive version''': |
||
< |
<syntaxhighlight lang="julia">function binom(n::Integer, k::Integer) |
||
n ≥ k || return 0 # short circuit base cases |
n ≥ k || return 0 # short circuit base cases |
||
n == 1 || k == 0 && return 1 |
(n == 1 || k == 0) && return 1 |
||
n * binom(n - 1, k - 1) ÷ k |
|||
end |
end |
||
@show binom(5, 3)</ |
@show binom(5, 3)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,231: | Line 1,506: | ||
=={{header|K}}== |
=={{header|K}}== |
||
< |
<syntaxhighlight lang="k"> {[n;k]_(*/(k-1)_1+!n)%(*/1+!k)} . 5 3 |
||
10</ |
10</syntaxhighlight> |
||
Alternative version: |
Alternative version: |
||
< |
<syntaxhighlight lang="k"> {[n;k]i:!(k-1);_*/((n-i)%(i+1))} . 5 3 |
||
10</ |
10</syntaxhighlight> |
||
Using Pascal's triangle: |
Using Pascal's triangle: |
||
< |
<syntaxhighlight lang="k"> pascal:{x{+':0,x,0}\1} |
||
pascal 5 |
pascal 5 |
||
(1 |
(1 |
||
Line 1,249: | Line 1,524: | ||
{[n;k](pascal n)[n;k]} . 5 3 |
{[n;k](pascal n)[n;k]} . 5 3 |
||
10</ |
10</syntaxhighlight> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
<lang |
<syntaxhighlight lang="scala">// version 2.0 |
||
fun factorial(n: Int) = when { |
|||
n < 0 -> throw IllegalArgumentException("negative numbers not allowed") |
|||
else -> { |
|||
var ans = 1L |
|||
for (i in 2..n) ans *= i |
|||
ans |
|||
} |
|||
} |
|||
fun binomial(n: Int, k: Int) = when { |
fun binomial(n: Int, k: Int) = when { |
||
Line 1,267: | Line 1,533: | ||
n == k -> 1L |
n == k -> 1L |
||
else -> { |
else -> { |
||
val kReduced = min(k, n - k) // minimize number of steps |
|||
var ans = 1L |
|||
var result = 1L |
|||
var numerator = n |
|||
var denominator = 1 |
|||
while (denominator <= kReduced) |
|||
result = result * numerator-- / denominator++ |
|||
result |
|||
} |
} |
||
} |
} |
||
Line 1,279: | Line 1,549: | ||
println() |
println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,299: | Line 1,569: | ||
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 |
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 |
||
</pre> |
</pre> |
||
=={{header|Lambdatalk}}== |
|||
<syntaxhighlight lang="scheme"> |
|||
{def C |
|||
{lambda {:n :p} |
|||
{/ {* {S.serie :n {- :n :p -1} -1}} |
|||
{* {S.serie :p 1 -1}}}}} |
|||
-> C |
|||
{C 16 8} |
|||
-> 12870 |
|||
1{S.map {lambda {:n} {br}1 |
|||
{S.map {C :n} {S.serie 1 {- :n 1}}} 1} |
|||
{S.serie 2 16}} |
|||
-> |
|||
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 |
|||
</syntaxhighlight> |
|||
=={{header|Lasso}}== |
=={{header|Lasso}}== |
||
< |
<syntaxhighlight lang="lasso">define binomial(n::integer,k::integer) => { |
||
#k == 0 ? return 1 |
#k == 0 ? return 1 |
||
local(result = 1) |
local(result = 1) |
||
Line 1,312: | Line 1,617: | ||
binomial(5, 3) |
binomial(5, 3) |
||
binomial(5, 4) |
binomial(5, 4) |
||
binomial(60, 30)</ |
binomial(60, 30)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,318: | Line 1,623: | ||
5 |
5 |
||
118264581564861424</pre> |
118264581564861424</pre> |
||
=={{header|Liberty BASIC}}== |
|||
<syntaxhighlight 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 |
|||
</syntaxhighlight> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang="logo">to choose :n :k |
||
if :k = 0 [output 1] |
if :k = 0 [output 1] |
||
output (choose :n :k-1) * (:n - :k + 1) / :k |
output (choose :n :k-1) * (:n - :k + 1) / :k |
||
Line 1,326: | Line 1,657: | ||
show choose 5 3 ; 10 |
show choose 5 3 ; 10 |
||
show choose 60 30 ; 1.18264581564861e+17</ |
show choose 60 30 ; 1.18264581564861e+17</syntaxhighlight> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">function Binomial( n, k ) |
||
if k > n then return nil end |
if k > n then return nil end |
||
if k > n/2 then k = n - k end -- (n k) = (n n-k) |
if k > n/2 then k = n - k end -- (n k) = (n n-k) |
||
Line 1,338: | Line 1,670: | ||
end |
end |
||
return numer / denom |
return numer / denom |
||
end</ |
end</syntaxhighlight> |
||
Additive recursion with memoization by hashing 2 input integer. |
Additive recursion with memoization by hashing 2 input integer. |
||
Lua 5.3 support bit-wise operation; assume 64 bit integer implementation here. |
Lua 5.3 support bit-wise operation; assume 64 bit integer implementation here. |
||
< |
<syntaxhighlight lang="lua">local Binomial = setmetatable({},{ |
||
__call = function(self,n,k) |
__call = function(self,n,k) |
||
local hash = (n<<32) | (k & 0xffffffff) |
local hash = (n<<32) | (k & 0xffffffff) |
||
Line 1,372: | Line 1,704: | ||
}) |
}) |
||
print( Binomial(100,50)) -- 1.0089134454556e+029 |
print( Binomial(100,50)) -- 1.0089134454556e+029 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|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> |
|||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">convert(binomial(n,k),factorial); |
||
binomial(5,3);</ |
binomial(5,3);</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> factorial(n) |
<pre> factorial(n) |
||
Line 1,413: | Line 1,718: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">(Local) In[1]:= Binomial[5,3] |
||
(Local) Out[1]= 10</ |
(Local) Out[1]= 10</syntaxhighlight> |
||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
Line 1,420: | Line 1,725: | ||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="matlab">>> nchoosek(5,3) |
||
ans = |
ans = |
||
10</ |
10</syntaxhighlight> |
||
Alternative implementations are: |
Alternative implementations are: |
||
< |
<syntaxhighlight lang="matlab">function r = binomcoeff1(n,k) |
||
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n |
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n |
||
r = r(k); |
r = r(k); |
||
end; </ |
end; </syntaxhighlight> |
||
< |
<syntaxhighlight lang="matlab">function r = binomcoeff2(n,k) |
||
prod((n-k+1:n)./(1:k)) |
prod((n-k+1:n)./(1:k)) |
||
end; </ |
end; </syntaxhighlight> |
||
< |
<syntaxhighlight lang="matlab">function r = binomcoeff3(n,k) |
||
m = pascal(max(n-k,k)+1); |
m = pascal(max(n-k,k)+1); |
||
r = m(n-k+1,k+1); |
r = m(n-k+1,k+1); |
||
end; </ |
end; </syntaxhighlight> |
||
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. |
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: |
binomialCoeff.m: |
||
< |
<syntaxhighlight lang="matlab">function coefficients = binomialCoeff(n,k) |
||
coefficients = zeros(numel(n),numel(k)); %Preallocate memory |
coefficients = zeros(numel(n),numel(k)); %Preallocate memory |
||
Line 1,462: | Line 1,767: | ||
end |
end |
||
end %binomialCoeff</ |
end %binomialCoeff</syntaxhighlight> |
||
Sample Usage: |
Sample Usage: |
||
< |
<syntaxhighlight lang="matlab">>> binomialCoeff((0:5),(0:5)) |
||
ans = |
ans = |
||
Line 1,503: | Line 1,808: | ||
ans = |
ans = |
||
10</ |
10</syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang="maxima">binomial( 5, 3); /* 10 */ |
||
binomial(-5, 3); /* -35 */ |
binomial(-5, 3); /* -35 */ |
||
binomial( 5, -3); /* 0 */ |
binomial( 5, -3); /* 0 */ |
||
Line 1,518: | Line 1,823: | ||
binomial(a, b); /* binomial(a, b) */ |
binomial(a, b); /* binomial(a, b) */ |
||
makegamma(%); /* gamma(a + 1)/(gamma(-b + a + 1)*gamma(b + 1)) */</ |
makegamma(%); /* gamma(a + 1)/(gamma(-b + a + 1)*gamma(b + 1)) */</syntaxhighlight> |
||
=={{header|min}}== |
=={{header|min}}== |
||
{{works with|min|0.19.3}} |
{{works with|min|0.19.3}} |
||
< |
<syntaxhighlight lang="min">((dup 0 ==) 'succ (dup pred) '* linrec) :fact |
||
('dup dip dup ((fact) () (- fact) (fact * div)) spread) :binomial |
('dup dip dup ((fact) () (- fact) (fact * div)) spread) :binomial |
||
5 3 binomial puts!</ |
5 3 binomial puts!</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
10 |
10 |
||
</pre> |
</pre> |
||
=={{header|МК-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'' В/О С/П. |
|||
=={{header|MINIL}}== |
=={{header|MINIL}}== |
||
< |
<syntaxhighlight lang="minil">// Number of combinations nCr |
||
00 0E Go: ENT R0 // n |
00 0E Go: ENT R0 // n |
||
01 1E ENT R1 // r |
01 1E ENT R1 // r |
||
Line 1,571: | Line 1,869: | ||
1D C9 JNZ Next |
1D C9 JNZ Next |
||
1E 03 R0 = R3 |
1E 03 R0 = R3 |
||
1F 80 JZ Go // Display result</ |
1F 80 JZ Go // Display result</syntaxhighlight> |
||
This uses the recursive definition: |
This uses the recursive definition: |
||
Line 1,580: | Line 1,878: | ||
which results from the definition of ncr in terms of factorials. |
which results from the definition of ncr in terms of factorials. |
||
=={{header|МК-61/52}}== |
|||
<syntaxhighlight lang="text">П1 <-> П0 ПП 22 П2 ИП1 ПП 22 П3 |
|||
ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3 |
|||
/ С/П ВП П0 1 ИП0 * L0 25 В/О</syntaxhighlight> |
|||
''Input'': ''n'' ^ ''k'' В/О С/П. |
|||
=={{header|Nanoquery}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="nanoquery">def binomialCoeff(n, k) |
|||
result = 1 |
|||
for i in range(1, k) |
|||
result = result * (n-i+1) / i |
|||
end |
|||
return result |
|||
end |
|||
if main |
|||
println binomialCoeff(5,3) |
|||
end</syntaxhighlight> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Note that a function to compute these coefficients, named “binom”, is available in standard module “math”. |
|||
<lang nim>proc binomialCoeff(n, k: int): int = |
|||
<syntaxhighlight lang="nim">proc binomialCoeff(n, k: int): int = |
|||
result = 1 |
result = 1 |
||
for i in 1..k: |
for i in 1..k: |
||
result = result * (n-i+1) div i |
result = result * (n-i+1) div i |
||
echo binomialCoeff(5, 3)</ |
echo binomialCoeff(5, 3)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|Oberon}}== |
=={{header|Oberon-2}}== |
||
{{works with|oo2c}} |
{{works with|oo2c}} |
||
< |
<syntaxhighlight lang="oberon2"> |
||
MODULE Binomial; |
MODULE Binomial; |
||
IMPORT |
IMPORT |
||
Line 1,615: | Line 1,935: | ||
Out.Int(For(5,2),0);Out.Ln |
Out.Int(For(5,2),0);Out.Ln |
||
END Binomial. |
END Binomial. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
<syntaxhighlight lang="ocaml"> |
|||
<lang OCaml> |
|||
let binomialCoeff n p = |
let binomialCoeff n p = |
||
let p = if p < n -. p then p else n -. p in |
let p = if p < n -. p then p else n -. p in |
||
Line 1,631: | Line 1,951: | ||
else res in |
else res in |
||
cm 1. n 1. |
cm 1. n 1. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=== Alternate version using big integers === |
=== Alternate version using big integers === |
||
< |
<syntaxhighlight lang="ocaml">#load "nums.cma";; |
||
open Num;; |
open Num;; |
||
Line 1,643: | Line 1,963: | ||
else a (succ j) ((v */ (Int (n - j))) // (Int (succ j))) |
else a (succ j) ((v */ (Int (n - j))) // (Int (succ j))) |
||
in a 0 (Int 1) |
in a 0 (Int 1) |
||
;;</ |
;;</syntaxhighlight> |
||
=== Simple recursive version === |
=== Simple recursive version === |
||
< |
<syntaxhighlight 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)</ |
let rec binomial n k = if n = k then Int 1 else ((binomial (n-1) k) */ Int n) // Int (n-k)</syntaxhighlight> |
||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">: binomial(n, k) | i | 1 k loop: i [ n i - 1+ * i / ] ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,662: | Line 1,981: | ||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="oz">declare |
||
fun {BinomialCoeff N K} |
fun {BinomialCoeff N K} |
||
{List.foldL {List.number 1 K 1} |
{List.foldL {List.number 1 K 1} |
||
Line 1,671: | Line 1,990: | ||
end |
end |
||
in |
in |
||
{Show {BinomialCoeff 5 3}}</ |
{Show {BinomialCoeff 5 3}}</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
<lang |
<syntaxhighlight lang="parigp">binomial(5,3)</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
Line 1,680: | Line 1,999: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">sub binomial { |
||
use bigint; |
use bigint; |
||
my ($r, $n, $k) = (1, @_); |
my ($r, $n, $k) = (1, @_); |
||
Line 1,687: | Line 2,006: | ||
} |
} |
||
print binomial(5, 3);</ |
print binomial(5, 3);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,693: | Line 2,012: | ||
Since the bigint module already has a binomial method, this could also be written as: |
Since the bigint module already has a binomial method, this could also be written as: |
||
< |
<syntaxhighlight lang="perl">sub binomial { |
||
use bigint; |
use bigint; |
||
my($n,$k) = @_; |
my($n,$k) = @_; |
||
(0+$n)->bnok($k); |
(0+$n)->bnok($k); |
||
}</ |
}</syntaxhighlight> |
||
For better performance, especially with large inputs, one can also use something like: |
For better performance, especially with large inputs, one can also use something like: |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/binomial/; |
||
print length(binomial(100000,50000)), "\n";</ |
print length(binomial(100000,50000)), "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>30101</pre> |
<pre>30101</pre> |
||
The Math::Pari module also has binomial, but it needs large amounts of added stack space for large arguments (this is due to using a very old version of the underlying Pari library). |
The Math::Pari module also has binomial, but it needs large amounts of added stack space for large arguments (this is due to using a very old version of the underlying Pari library). |
||
=={{header|Perl 6}}== |
|||
For a start, you can get the length of the corresponding list of combinations: |
|||
<lang perl6>say combinations(5, 3).elems;</lang> |
|||
{{out}} |
|||
<pre>10</pre> |
|||
This method is efficient, as Perl 6 will not actually compute each element of the list, since it actually uses an iterator with a defined <tt>count-only</tt> method. Such method performs computations in a way similar to the following infix operator: |
|||
<lang perl6>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. $^p } |
|||
say 5 choose 3;</lang> |
|||
A possible optimization would use a symmetry property of the binomial coefficient: |
|||
<lang perl6>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p) }</lang> |
|||
One drawback of this method is that it returns a Rat, not an Int. So we actually may want to enforce the conversion: |
|||
<lang perl6>sub infix:<choose> { ([*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p)).Int }</lang> |
|||
And ''this'' is exactly what the <tt>count-only</tt> method does. |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
There is a builtin choose() function which does this. From builtins/factorial.e (an autoinclude): |
|||
A naive version: |
|||
<!--<syntaxhighlight lang="phix">--> |
|||
<lang Phix>function binom(integer n, k) |
|||
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #000000;">choose</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> |
|||
return factorial(n)/(factorial(k)*factorial(n-k)) |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
end function |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))/</span><span style="color: #000000;">i</span> |
|||
?binom(5,3)</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<!--</syntaxhighlight>--> |
|||
Example: |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">choose</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
10 |
10 |
||
</pre> |
</pre> |
||
However errors will creep in should any result or interim value exceed 9,007,199,254,740,992 (on 32-bit), so |
However errors will creep in should any result or interim value exceed 9,007,199,254,740,992 (on 32-bit), so: |
||
{{libheader| |
{{libheader|Phix/mpfr}} |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>include builtins\bigatom.e |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
function ba_binom(integer n, k) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">120</span><span style="color: #0000FF;">}}</span> |
|||
bigatom r = ba_new(1) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
for i=1 to k do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
r = ba_divide(ba_multiply(r,n-i+1),i) |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #7060A8;">mpz_bin_uiui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> |
|||
return r |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
?ba_sprintf("%B",ba_binom(5,3)) |
|||
?ba_sprintf("%B",ba_binom(100,50)) |
|||
?ba_sprintf("%B",ba_binom(60,30)) |
|||
?ba_sprintf("%B",ba_binom(1200,120))</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,762: | Line 2,066: | ||
"1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600" |
"1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600" |
||
</pre> |
</pre> |
||
Note that I have re-implemented mpz_bin_uiui() mainly for the benefit of pwa/p2js, and some tweaks may be in order (please ask if needed) to match gmp proper for -ve n. |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
$n=5; |
$n=5; |
||
$k=3; |
$k=3; |
||
Line 1,773: | Line 2,078: | ||
$binomial_coefficient=factorial($n)/(factorial($k)*factorial($n-$k)); |
$binomial_coefficient=factorial($n)/(factorial($k)*factorial($n-$k)); |
||
echo $binomial_coefficient; |
echo $binomial_coefficient; |
||
?></ |
?></syntaxhighlight> |
||
Alternative version, not based on factorial |
Alternative version, not based on factorial |
||
<syntaxhighlight lang="php"> |
|||
<lang PHP> |
|||
function binomial_coefficient($n, $k) { |
function binomial_coefficient($n, $k) { |
||
if ($k == 0) return 1; |
if ($k == 0) return 1; |
||
Line 1,785: | Line 2,090: | ||
return $result; |
return $result; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Picat}}== |
|||
===Iterative=== |
|||
<syntaxhighlight lang="picat">binomial_it(N,K) = Res => |
|||
if K < 0 ; K > N then |
|||
R = 0 |
|||
else |
|||
R = 1, |
|||
foreach(I in 0..K-1) |
|||
R := R * (N-I) // (I+1) |
|||
end |
|||
end, |
|||
Res = R.</syntaxhighlight> |
|||
===Using built-in factorial/1=== |
|||
<syntaxhighlight lang="picat">binomial_fac(N,K) = factorial(N) // factorial(K) // factorial(N-K).</syntaxhighlight> |
|||
===Recursion (tabled)=== |
|||
<syntaxhighlight lang="picat">table |
|||
binomial_rec(_N, 0) = 1. |
|||
binomial_rec(0, _K) = 0. |
|||
binomial_rec(N, K) = binomial_rec(N-1,K-1) + binomial_rec(N-1,K).</syntaxhighlight> |
|||
===Test=== |
|||
<syntaxhighlight lang="picat">go => |
|||
Tests = [[10,3],[60,30],[100,50],[400,200]], |
|||
foreach([N,K] in Tests) |
|||
println([N,K,binomial_it(N,K)]) |
|||
end, |
|||
nl. |
|||
</syntaxhighlight> |
|||
All methods prints the same result. |
|||
{{out}} |
|||
<pre> |
|||
[10,3,120] |
|||
[60,30,118264581564861424] |
|||
[100,50,100891344545564193334812497256] |
|||
[400,200,102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120]</pre> |
|||
binomial_rec/2 is a little slower than the two other (0.036s vs 0.002s on these tests). |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de binomial (N K) |
||
(let f |
(let f |
||
'((N) |
'((N) |
||
Line 1,794: | Line 2,143: | ||
(/ |
(/ |
||
(f N) |
(f N) |
||
(* (f (- N K)) (f K)) ) ) )</ |
(* (f (- N K)) (f K)) ) ) )</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>: (binomial 5 3) |
<pre>: (binomial 5 3) |
||
Line 1,800: | Line 2,149: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
binomial_coefficients: |
binomial_coefficients: |
||
procedure options (main); |
procedure options (main); |
||
Line 1,823: | Line 2,172: | ||
end fact; |
end fact; |
||
end binomial_coefficients; |
end binomial_coefficients; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,830: | Line 2,179: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function choose($n,$k) { |
function choose($n,$k) { |
||
if($k -le $n -and 0 -le $k) { |
if($k -le $n -and 0 -le $k) { |
||
Line 1,848: | Line 2,197: | ||
choose 10 2 |
choose 10 2 |
||
choose 10 8 |
choose 10 8 |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 1,859: | Line 2,208: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Procedure Factor(n) |
||
Protected Result=1 |
Protected Result=1 |
||
While n>0 |
While n>0 |
||
Line 1,879: | Line 2,228: | ||
Print("Press ENTER to quit"): Input() |
Print("Press ENTER to quit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
'''Example |
'''Example |
||
Enter value n: 5 |
Enter value n: 5 |
||
Line 1,887: | Line 2,236: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Imperative=== |
===Imperative=== |
||
< |
<syntaxhighlight lang="python">def binomialCoeff(n, k): |
||
result = 1 |
result = 1 |
||
for i in range(1, k+1): |
for i in range(1, k+1): |
||
Line 1,894: | Line 2,243: | ||
if __name__ == "__main__": |
if __name__ == "__main__": |
||
print(binomialCoeff(5, 3))</ |
print(binomialCoeff(5, 3))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
===Functional=== |
===Functional=== |
||
< |
<syntaxhighlight lang="python">from operator import mul |
||
from functools import reduce |
from functools import reduce |
||
Line 1,921: | Line 2,270: | ||
else: |
else: |
||
return ( reduce( mul, range((n - r + 1), n + 1), 1) |
return ( reduce( mul, range((n - r + 1), n + 1), 1) |
||
// reduce( mul, range(1, r + 1), 1) )</ |
// reduce( mul, range(1, r + 1), 1) )</syntaxhighlight> |
||
Line 1,927: | Line 2,276: | ||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Evaluation of binomial coefficients''' |
||
from functools import reduce |
from functools import reduce |
||
Line 1,986: | Line 2,335: | ||
# TESTS --------------------------------------------------- |
# TESTS --------------------------------------------------- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10 |
<pre>10 |
||
Line 1,993: | Line 2,342: | ||
Compare the use of Python comments, (above); with the use of Python type hints, (below). |
Compare the use of Python comments, (above); with the use of Python type hints, (below). |
||
< |
<syntaxhighlight lang="python">from typing import (Callable, List, Any) |
||
from functools import reduce |
from functools import reduce |
||
from operator import mul |
from operator import mul |
||
Line 2,017: | Line 2,366: | ||
print(binomialCoefficient(5)(3)) |
print(binomialCoefficient(5)(3)) |
||
# k=0 to k=5, where n=5 |
# k=0 to k=5, where n=5 |
||
print(list(map(binomialCoefficient(5), enumFromTo(0)(5))))</ |
print(list(map(binomialCoefficient(5), enumFromTo(0)(5))))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10 |
<pre>10 |
||
[1, 5, 10, 10, 5, 1]</pre> |
[1, 5, 10, 10, 5, 1]</pre> |
||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery"> [ tuck - over |
|||
1 swap times |
|||
[ over i + 1+ * ] |
|||
nip swap times |
|||
[ i 1+ / ] ] is binomial ( n n --> ) |
|||
5 3 binomial echo</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10</pre> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
R's built-in choose() function evaluates binomial coefficients: |
R's built-in choose() function evaluates binomial coefficients: |
||
<lang |
<syntaxhighlight lang="r">choose(5,3)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,030: | Line 2,394: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(require math) |
(require math) |
||
(binomial 10 5) |
(binomial 10 5) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
For a start, you can get the length of the corresponding list of combinations: |
|||
<syntaxhighlight lang="raku" line>say combinations(5, 3).elems;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10</pre> |
|||
This method is efficient, as Raku will not actually compute each element of the list, since it actually uses an iterator with a defined <tt>count-only</tt> method. Such method performs computations in a way similar to the following infix operator: |
|||
<syntaxhighlight lang="raku" line>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. $^p } |
|||
say 5 choose 3;</syntaxhighlight> |
|||
A possible optimization would use a symmetry property of the binomial coefficient: |
|||
<syntaxhighlight lang="raku" line>sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p) }</syntaxhighlight> |
|||
One drawback of this method is that it returns a Rat, not an Int. So we actually may want to enforce the conversion: |
|||
<syntaxhighlight lang="raku" line>sub infix:<choose> { ([*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p)).Int }</syntaxhighlight> |
|||
And ''this'' is exactly what the <tt>count-only</tt> method does. |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits. |
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits. |
||
===idiomatic=== |
===idiomatic=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates binomial coefficients (also known as combinations). */ |
||
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
||
parse arg n k . /*obtain N and K from the C.L. */ |
parse arg n k . /*obtain N and K from the C.L. */ |
||
Line 2,046: | Line 2,431: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y)) |
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y)) |
||
!: procedure; !=1; do j=2 to arg(1); !=!*j; end /*j*/; return !</ |
!: procedure; !=1; do j=2 to arg(1); !=!*j; end /*j*/; return !</syntaxhighlight> |
||
'''output''' when using the input of: <tt> 5 3 </tt> |
'''output''' when using the input of: <tt> 5 3 </tt> |
||
<pre> |
<pre> |
||
Line 2,059: | Line 2,444: | ||
This REXX version takes advantage of reducing the size (product) of the numerator, and also, |
This REXX version takes advantage of reducing the size (product) of the numerator, and also, |
||
<br>only two (factorial) products need be calculated. |
<br>only two (factorial) products need be calculated. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates binomial coefficients (also known as combinations). */ |
||
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
numeric digits 100000 /*be able to handle gihugeic numbers. */ |
||
parse arg n k . /*obtain N and K from the C.L. */ |
parse arg n k . /*obtain N and K from the C.L. */ |
||
Line 2,067: | Line 2,452: | ||
comb: procedure; parse arg x,y; return pfact(x-y+1, x) % pfact(2, y) |
comb: procedure; parse arg x,y; return pfact(x-y+1, x) % pfact(2, y) |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end /*j*/; return !</ |
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end /*j*/; return !</syntaxhighlight> |
||
'''output''' is identical to the 1<sup>st</sup> REXX version. |
'''output''' is identical to the 1<sup>st</sup> REXX version. |
||
Line 2,074: | Line 2,459: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
numer = 0 |
numer = 0 |
||
binomial(5,3) |
binomial(5,3) |
||
Line 2,087: | Line 2,472: | ||
next |
next |
||
return numer |
return numer |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|RPL}}== |
|||
RPL has a <code>COMB</code> instruction which returns the result directly. If a home-made function is preferred, there are many possibilities. |
|||
Using the recommended formula and the stack: |
|||
≪ - LAST ! SWAP ! SWAP ROT ! * / ≫ ‘'''CHOOS'''’ STO |
|||
Using the formula with local variables: |
|||
≪ → n k ≪ n ! n k - ! / k ! / ≫ ≫ ‘'''CHOOS'''’ STO |
|||
To avoid data overflow for high values of n, using the formula simplified by (n-k)! : |
|||
≪ → n k ≪ 1 n k - 1 + n '''FOR''' j j * '''NEXT''' k ! / ≫ ≫ ‘'''CHOOS'''’ STO |
|||
All the above functions are called the same way and return the same result: |
|||
5 3 '''CHOOS''' |
|||
{{out}} |
|||
<pre> |
|||
10 |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Line 2,093: | Line 2,494: | ||
{{works with|Ruby|1.8.7+}} |
{{works with|Ruby|1.8.7+}} |
||
< |
<syntaxhighlight lang="ruby">class Integer |
||
# binomial coefficient: n C k |
# binomial coefficient: n C k |
||
def choose(k) |
def choose(k) |
||
Line 2,105: | Line 2,506: | ||
p 5.choose(3) |
p 5.choose(3) |
||
p 60.choose(30)</ |
p 60.choose(30)</syntaxhighlight> |
||
result |
result |
||
<pre>10 |
<pre>10 |
||
Line 2,112: | Line 2,513: | ||
another implementation: |
another implementation: |
||
< |
<syntaxhighlight lang="ruby"> |
||
def c n, r |
def c n, r |
||
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end |
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end |
||
end |
end |
||
</ |
</syntaxhighlight>Ruby's Arrays have a combination method which result in a (lazy) enumerator. This Enumerator has a "size" method, which returns the size of the enumerator, or nil if it can’t be calculated lazily. (Since Ruby 2.0) |
||
< |
<syntaxhighlight lang="ruby">(1..60).to_a.combination(30).size #=> 118264581564861424</syntaxhighlight> |
||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">print "binomial (5,1) = "; binomial(5, 1) |
||
print "binomial (5,2) = "; binomial(5, 2) |
print "binomial (5,2) = "; binomial(5, 2) |
||
print "binomial (5,3) = "; binomial(5, 3) |
print "binomial (5,3) = "; binomial(5, 3) |
||
Line 2,136: | Line 2,537: | ||
next i |
next i |
||
binomial = coeff |
binomial = coeff |
||
end function</ |
end function</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>binomial (5,1) = 5 |
<pre>binomial (5,1) = 5 |
||
Line 2,145: | Line 2,546: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">fn fact(n:u32) -> u64 { |
||
let mut f:u64 = n as u64; |
let mut f:u64 = n as u64; |
||
for i in 2..n { |
for i in 2..n { |
||
Line 2,163: | Line 2,564: | ||
fn main() { |
fn main() { |
||
println!("{}", choose(5,3)); |
println!("{}", choose(5,3)); |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
Line 2,169: | Line 2,570: | ||
Alternative version, using functional style: |
Alternative version, using functional style: |
||
< |
<syntaxhighlight lang="rust">fn choose(n:u64,k:u64)->u64 { |
||
let factorial=|x| (1..=x).fold(1, |a, x| a * x); |
let factorial=|x| (1..=x).fold(1, |a, x| a * x); |
||
factorial(n) / factorial(k) / factorial(n - k) |
factorial(n) / factorial(k) / factorial(n - k) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">object Binomial { |
||
def main(args: Array[String]): Unit = { |
def main(args: Array[String]): Unit = { |
||
val n=5 |
val n=5 |
||
Line 2,185: | Line 2,586: | ||
def binomialCoefficient(n:Int, k:Int)=fact(n) / (fact(k) * fact(n-k)) |
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) |
def fact(n:Int):Int=if (n==0) 1 else n*fact(n-1) |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>The Binomial Coefficient of 5 and 3 equals 10.</pre> |
<pre>The Binomial Coefficient of 5 and 3 equals 10.</pre> |
||
Line 2,191: | Line 2,592: | ||
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: |
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: |
||
< |
<syntaxhighlight lang="scala">object Binomial extends App { |
||
def binomialCoefficient(n: Int, k: Int) = |
def binomialCoefficient(n: Int, k: Int) = |
||
(BigInt(n - k + 1) to n).product / |
(BigInt(n - k + 1) to n).product / |
||
Line 2,198: | Line 2,599: | ||
val Array(n, k) = args.map(_.toInt) |
val Array(n, k) = args.map(_.toInt) |
||
println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k))) |
println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k))) |
||
}</ |
}</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,205: | Line 2,606: | ||
Using recursive formula <code>C(n,k) = C(n-1,k-1) + C(n-1,k)</code>: |
Using recursive formula <code>C(n,k) = C(n-1,k-1) + C(n-1,k)</code>: |
||
< |
<syntaxhighlight lang="scala"> def bico(n: Long, k: Long): Long = (n, k) match { |
||
case (n, 0) => 1 |
case (n, 0) => 1 |
||
case (0, k) => 0 |
case (0, k) => 0 |
||
case (n, k) => bico(n - 1, k - 1) + bico(n - 1, k) |
case (n, k) => bico(n - 1, k - 1) + bico(n - 1, k) |
||
} |
} |
||
println("bico(5,3) = " + bico(5, 3))</ |
println("bico(5,3) = " + bico(5, 3))</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>bico(5,3) = 10</pre> |
<pre>bico(5,3) = 10</pre> |
||
Line 2,216: | Line 2,617: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{Works with|Scheme|R<math>^5</math>RS}} |
{{Works with|Scheme|R<math>^5</math>RS}} |
||
< |
<syntaxhighlight lang="scheme">(define (factorial n) |
||
(define (*factorial n acc) |
(define (*factorial n acc) |
||
(if (zero? n) |
(if (zero? n) |
||
Line 2,227: | Line 2,628: | ||
(display (choose 5 3)) |
(display (choose 5 3)) |
||
(newline)</ |
(newline)</syntaxhighlight> |
||
{{Out}} |
|||
<pre>10</pre> |
|||
Alternatively a recursive implementation can be constructed from Pascal's Triangle: |
|||
<syntaxhighlight lang="scheme">(define (pascal i j) |
|||
(cond ((= i 0) 1) |
|||
((= j 0) 1) |
|||
(else (+ |
|||
(pascal (- i 1) j) |
|||
(pascal i (- j 1)))))) |
|||
(define (choose n k) |
|||
(pascal (- n k) k))) |
|||
(display (choose 5 3)) |
|||
(newline)</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>10</pre> |
<pre>10</pre> |
||
Line 2,236: | Line 2,654: | ||
E.g.: <tt>(-6) ! 10</tt> evaluates to 3003. |
E.g.: <tt>(-6) ! 10</tt> evaluates to 3003. |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const proc: main is func |
const proc: main is func |
||
Line 2,249: | Line 2,667: | ||
writeln; |
writeln; |
||
end for; |
end for; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,281: | Line 2,699: | ||
for the type [http://seed7.sourceforge.net/manual/types.htm#bigInteger bigInteger]: |
for the type [http://seed7.sourceforge.net/manual/types.htm#bigInteger bigInteger]: |
||
< |
<syntaxhighlight lang="seed7">const func bigInteger: (in bigInteger: n) ! (in var bigInteger: k) is func |
||
result |
result |
||
var bigInteger: binom is 0_; |
var bigInteger: binom is 0_; |
||
Line 2,307: | Line 2,725: | ||
end if; |
end if; |
||
end func; |
end func; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Original source [http://seed7.sourceforge.net/algorith/math.htm#binomial_coefficient]. |
Original source [http://seed7.sourceforge.net/algorith/math.htm#binomial_coefficient]. |
||
Line 2,314: | Line 2,732: | ||
Simplest Solution: |
Simplest Solution: |
||
<syntaxhighlight lang="sequencel"> |
|||
<lang sequenceL> |
|||
choose(n, k) := product(k + 1 ... n) / product(1 ... n - k); |
choose(n, k) := product(k + 1 ... n) / product(1 ... n - k); |
||
</syntaxhighlight> |
|||
</lang> |
|||
Tail-Recursive solution to avoid arithmetic with large integers: |
Tail-Recursive solution to avoid arithmetic with large integers: |
||
<syntaxhighlight lang="sequencel"> |
|||
<lang sequenceL> |
|||
choose(n,k) := binomial(n, k, 1, 1); |
choose(n,k) := binomial(n, k, 1, 1); |
||
Line 2,326: | Line 2,744: | ||
result when i > k else |
result when i > k else |
||
binomial(n, k, i + 1, (result * (n - i + 1)) / i); |
binomial(n, k, i + 1, (result * (n - i + 1)) / i); |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Straightforward translation of the formula: |
Straightforward translation of the formula: |
||
< |
<syntaxhighlight lang="ruby">func binomial(n,k) { |
||
n! / ((n-k)! * k!) |
n! / ((n-k)! * k!) |
||
} |
} |
||
say binomial(400, 200)</ |
say binomial(400, 200)</syntaxhighlight> |
||
Alternatively, by using the ''Number.nok()'' method: |
Alternatively, by using the ''Number.nok()'' method: |
||
<lang |
<syntaxhighlight lang="ruby">say 400.nok(200)</syntaxhighlight> |
||
=={{header|Smalltalk}}== |
|||
{{works with|Smalltalk/X}} |
|||
Having a small language but a big class library in my bag, we can write: |
|||
<syntaxhighlight lang="smalltalk">Transcript showCR: (5 binco:3). |
|||
Transcript showCR: (400 binco:200)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10 |
|||
102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120</pre> |
|||
A naïve implementation (in the Integer class) might look like: |
|||
<syntaxhighlight lang="smalltalk">binco:arg |
|||
^ (self factorial) / (arg factorial * (self-arg) factorial)</syntaxhighlight> |
|||
=={{header|Standard ML}}== |
|||
<syntaxhighlight lang="standardml"> |
|||
fun binomial n k = |
|||
if k > n then 0 else |
|||
let fun f (_, 0) = 1 |
|||
| f (i, d) = f (i + 1, d - 1) * i div d |
|||
in f (n - k + 1, k) end |
|||
</syntaxhighlight> |
|||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
Use the [http://www.stata.com/help.cgi?comb comb] function. Notice the result is a missing value if k>n or k<0. |
Use the [http://www.stata.com/help.cgi?comb comb] function. Notice the result is a missing value if k>n or k<0. |
||
< |
<syntaxhighlight lang="stata">. display comb(5,3) |
||
10</ |
10</syntaxhighlight> |
||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">func factorial<T: BinaryInteger>(_ n: T) -> T { |
|||
guard n != 0 else { |
|||
return 1 |
|||
} |
|||
return stride(from: n, to: 0, by: -1).reduce(1, *) |
|||
} |
|||
func binomial<T: BinaryInteger>(_ x: (n: T, k: T)) -> T { |
|||
let nFac = factorial(x.n) |
|||
let kFac = factorial(x.k) |
|||
return nFac / (factorial(x.n - x.k) * kFac) |
|||
} |
|||
print("binomial(\(5), \(3)) = \(binomial((5, 3)))") |
|||
print("binomial(\(20), \(11)) = \(binomial((20, 11)))")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>binomial(5, 3) = 10 |
|||
binomial(20, 11) = 167960</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
This uses exact arbitrary precision integer arithmetic. |
This uses exact arbitrary precision integer arithmetic. |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc binom {n k} { |
proc binom {n k} { |
||
# Compute the top half of the division; this is n!/(n-k)! |
# Compute the top half of the division; this is n!/(n-k)! |
||
Line 2,363: | Line 2,828: | ||
# Integer arithmetic divide is correct here; the factors always cancel out |
# Integer arithmetic divide is correct here; the factors always cancel out |
||
return [expr {$pTop / $pBottom}] |
return [expr {$pTop / $pBottom}] |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl">puts "5_C_3 = [binom 5 3]" |
||
puts "60_C_30 = [binom 60 30]"</ |
puts "60_C_30 = [binom 60 30]"</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>5_C_3 = 10 |
<pre>5_C_3 = 10 |
||
60_C_30 = 118264581564861424</pre> |
60_C_30 = 118264581564861424</pre> |
||
=={{header|TI-57}}== |
|||
{| class="wikitable" |
|||
! Machine code |
|||
! Comment |
|||
|- |
|||
| |
|||
'''Lbl 9''' |
|||
STO 2 |
|||
x⮂t |
|||
STO 1 |
|||
SBR 0 |
|||
STO 3 |
|||
RCL 1 |
|||
- |
|||
RCL 2 |
|||
= |
|||
SBR 0 |
|||
INV Prd 3 |
|||
RCL 2 |
|||
SBR 0 |
|||
Inv Prd 3 |
|||
RCL 3 |
|||
R/S |
|||
RST |
|||
'''Lbl 0''' |
|||
C.t |
|||
x=t |
|||
1 |
|||
STO 0 |
|||
'''Lbl 1''' |
|||
RCL 0 |
|||
× |
|||
Dsz |
|||
GTO 1 |
|||
1 |
|||
= |
|||
INV SBR |
|||
| |
|||
'''program binomial(x,t)''' // x is the display register |
|||
r2 = x |
|||
swap x and t |
|||
r1 = x |
|||
x = factorial(x) |
|||
r3 = x |
|||
x = r1 - r2 |
|||
x = factorial(x) |
|||
r3 /= x |
|||
x = r2 |
|||
x = factorial(x) |
|||
r3 /= x |
|||
x = r3 |
|||
end program |
|||
reset pointer |
|||
'''program factorial(x)''' |
|||
t=0 |
|||
if x=0 then |
|||
x=1 |
|||
r0 = x |
|||
loop |
|||
multiply r0 by what will be in the next loop |
|||
decrement r0 and exit loop if r0 = 0 |
|||
end loop |
|||
complete the multiplication sequence |
|||
return x! |
|||
end sub |
|||
|} |
|||
<code> 5 </code> <code>x⮂t</code> <code> 3 </code> <code>GTO</code> <code> 9 </code> <code>R/S</code> |
|||
{{out}} |
|||
<pre> |
|||
10. |
|||
</pre> |
|||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
||
Builtin operator nCr gives the number of combinations. |
Builtin operator nCr gives the number of combinations. |
||
<lang |
<syntaxhighlight lang="ti83b">10 nCr 4</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,383: | Line 2,924: | ||
Builtin function. |
Builtin function. |
||
<lang |
<syntaxhighlight lang="ti89b">nCr(n,k)</syntaxhighlight> |
||
=={{header|TXR}}== |
=={{header|TXR}}== |
||
Line 2,389: | Line 2,930: | ||
nCk is a built-in function, along with the one for permutations, nPk: |
nCk is a built-in function, along with the one for permutations, nPk: |
||
< |
<syntaxhighlight lang="sh">$ txr -p '(n-choose-k 20 15)' |
||
15504</ |
15504</syntaxhighlight> |
||
< |
<syntaxhighlight lang="sh">$ txr -p '(n-perm-k 20 15)' |
||
20274183401472000</ |
20274183401472000</syntaxhighlight> |
||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
< |
<syntaxhighlight lang="sh">#!/bin/sh |
||
n=5; |
n=5; |
||
k=3; |
k=3; |
||
Line 2,416: | Line 2,957: | ||
binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial ) |
binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial ) |
||
echo "Binomial Coefficient ($n,$k) = $binomial_coefficient"</ |
echo "Binomial Coefficient ($n,$k) = $binomial_coefficient"</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
A function for computing binomial coefficients (<code>choose</code>) 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. |
A function for computing binomial coefficients (<code>choose</code>) 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. |
||
< |
<syntaxhighlight lang="ursala">#import nat |
||
choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~</ |
choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~</syntaxhighlight> |
||
The standard library functions <code>quotient</code>, <code>product</code> and <code>predecessor</code> pertain to natural numbers in the obvious way. |
The standard library functions <code>quotient</code>, <code>product</code> and <code>predecessor</code> pertain to natural numbers in the obvious way. |
||
* <code>choose</code> is defined using the recursive conditional combinator (<code>^?</code>) as a function taking a pair of numbers, with the predicate <code>~&ar</code> testing whether the number on the right side of the pair is non-zero. |
* <code>choose</code> is defined using the recursive conditional combinator (<code>^?</code>) as a function taking a pair of numbers, with the predicate <code>~&ar</code> testing whether the number on the right side of the pair is non-zero. |
||
Line 2,434: | Line 2,973: | ||
* The product of these values is then divided (<code>quotient</code>) by the right side (<code>~&ar</code>) of the original argument and returned as the result. |
* The product of these values is then divided (<code>quotient</code>) by the right side (<code>~&ar</code>) of the original argument and returned as the result. |
||
Here is a less efficient implementation more closely following the formula above. |
Here is a less efficient implementation more closely following the formula above. |
||
< |
<syntaxhighlight lang="ursala">choose = quotient^/factorial@l product+ factorial^~/difference ~&r</syntaxhighlight> |
||
* <code>choose</code> is defined as the <code>quotient</code> of the results of a pair (<code>^</code>) of functions. |
* <code>choose</code> is defined as the <code>quotient</code> of the results of a pair (<code>^</code>) of functions. |
||
* The left function contributing to the quotient is the <code>factorial</code> of the left side (<code>@l</code>) of the argument, which is assumed to be a pair of natural numbers. The <code>factorial</code> function is provided in a standard library. |
* The left function contributing to the quotient is the <code>factorial</code> of the left side (<code>@l</code>) of the argument, which is assumed to be a pair of natural numbers. The <code>factorial</code> function is provided in a standard library. |
||
Line 2,442: | Line 2,981: | ||
* A composition (<code>+</code>) of this function with the <code>product</code> function effects the multiplication of the two factorials, to complete the other input to the quotient. |
* A composition (<code>+</code>) of this function with the <code>product</code> 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 (<code>~~</code>) operator. |
Here is an equivalent implementation using pattern matching, dummy variables, and only the apply-to-both (<code>~~</code>) operator. |
||
< |
<syntaxhighlight lang="ursala">choose("n","k") = quotient(factorial "n",product factorial~~ (difference("n","k"),"k"))</syntaxhighlight> |
||
test program: |
test program: |
||
< |
<syntaxhighlight lang="ursala">#cast %nL |
||
main = choose* <(5,3),(60,30)></ |
main = choose* <(5,3),(60,30)></syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre><10,118264581564861424></pre> |
<pre><10,118264581564861424></pre> |
||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">Function binomial(n,k) |
||
binomial = factorial(n)/(factorial(n-k)*factorial(k)) |
binomial = factorial(n)/(factorial(n-k)*factorial(k)) |
||
End Function |
End Function |
||
Line 2,471: | Line 3,010: | ||
'calling the function |
'calling the function |
||
WScript.StdOut.Write "the binomial coefficient of 5 and 3 = " & binomial(5,3) |
WScript.StdOut.Write "the binomial coefficient of 5 and 3 = " & binomial(5,3) |
||
WScript.StdOut.WriteLine</ |
WScript.StdOut.WriteLine</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>the binomial coefficient of 5 and 3 = 10</pre> |
<pre>the binomial coefficient of 5 and 3 = 10</pre> |
||
=={{header|Wren}}== |
|||
{{libheader|Wren-fmt}} |
|||
{{libheader|Wren-math}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
import "./math" for Int |
|||
var binomial = Fn.new { |n, k| |
|||
if (n < 0 || k < 0) Fiber.abort("Arguments must be non-negative integers") |
|||
if (n < k) Fiber.abort("The second argument cannot be more than the first.") |
|||
if (n == k) return 1 |
|||
var prod = 1 |
|||
var i = n - k + 1 |
|||
while (i <= n) { |
|||
prod = prod * i |
|||
i = i + 1 |
|||
} |
|||
return prod / Int.factorial(k) |
|||
} |
|||
var limit = 14 |
|||
System.write("n/k |") |
|||
for (k in 0..limit) System.write(Fmt.d(5, k)) |
|||
System.print() |
|||
System.write("----+" + "-----" * (limit + 1)) |
|||
System.print() |
|||
for (n in 0..limit) { |
|||
System.write("%(Fmt.d(3, n)) |") |
|||
for (k in 0..n) System.write(Fmt.d(5, binomial.call(n, k))) |
|||
System.print() |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
n/k | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|||
----+--------------------------------------------------------------------------- |
|||
0 | 1 |
|||
1 | 1 1 |
|||
2 | 1 2 1 |
|||
3 | 1 3 3 1 |
|||
4 | 1 4 6 4 1 |
|||
5 | 1 5 10 10 5 1 |
|||
6 | 1 6 15 20 15 6 1 |
|||
7 | 1 7 21 35 35 21 7 1 |
|||
8 | 1 8 28 56 70 56 28 8 1 |
|||
9 | 1 9 36 84 126 126 84 36 9 1 |
|||
10 | 1 10 45 120 210 252 210 120 45 10 1 |
|||
11 | 1 11 55 165 330 462 462 330 165 55 11 1 |
|||
12 | 1 12 66 220 495 792 924 792 495 220 66 12 1 |
|||
13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 |
|||
14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 |
|||
</pre> |
|||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">code ChOut=8, CrLf=9, IntOut=11; |
||
func Binomial(N, K); |
func Binomial(N, K); |
||
Line 2,499: | Line 3,089: | ||
CrLf(0); |
CrLf(0); |
||
]; |
]; |
||
] \Mr. Pascal's triangle!</ |
] \Mr. Pascal's triangle!</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 2,515: | Line 3,105: | ||
</pre> |
</pre> |
||
=={{header|Zig}}== |
|||
A reasonable implementation for a fixed word size is to precompute all possible values of nCk, since even on a 64 bit machine there's only 67 rows of Pascal's triangle to consider, or ~18K of data. |
|||
In Zig it's possible to compute all values of nCk at compile time, so that at runtime it's only necessary to do a table lookup. Zig also supports nullable values, so nCk can return a null value if the programmer requests a value that's out of range. Finally, since this code uses addition to compute the table, all entries that can fit in 64 bits can be computed, in contrast to some other code examples that may overflow before the maximum representable value (67 choose 33) is reached. For example, the largest value the BCPL version can compute is 61 choose 31. |
|||
<syntaxhighlight lang="zig"> |
|||
const std = @import("std"); |
|||
pub fn binomial(n: u32) ?[]const u64 { |
|||
if (n >= rmax) |
|||
return null |
|||
else { |
|||
const k = n * (n + 1) / 2; |
|||
return pascal[k .. k + n + 1]; |
|||
} |
|||
} |
|||
pub fn nCk(n: u32, k: u32) ?u64 { |
|||
if (n >= rmax) |
|||
return null |
|||
else if (k > n) |
|||
return 0 |
|||
else { |
|||
const j = n * (n + 1) / 2; |
|||
return pascal[j + k]; |
|||
} |
|||
} |
|||
const rmax = 68; |
|||
const pascal = build: { |
|||
@setEvalBranchQuota(100_000); |
|||
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined; |
|||
coefficients[0] = 1; |
|||
var j: u32 = 0; |
|||
var k: u32 = 1; |
|||
var n: u32 = 1; |
|||
while (n < rmax) : (n += 1) { |
|||
var prev = coefficients[j .. j + n]; |
|||
var next = coefficients[k .. k + n + 1]; |
|||
next[0] = 1; |
|||
var i: u32 = 1; |
|||
while (i < n) : (i += 1) |
|||
next[i] = prev[i] + prev[i - 1]; |
|||
next[i] = 1; |
|||
j = k; |
|||
k += n + 1; |
|||
} |
|||
break :build coefficients; |
|||
}; |
|||
test "n choose k" { |
|||
const expect = std.testing.expect; |
|||
try expect(nCk(10, 5).? == 252); |
|||
try expect(nCk(10, 11).? == 0); |
|||
try expect(nCk(10, 10).? == 1); |
|||
try expect(nCk(67, 33).? == 14226520737620288370); |
|||
try expect(nCk(68, 34) == null); |
|||
} |
|||
</syntaxhighlight> |
|||
Rather than write driver code, it's possible to run the unit test for this module. |
|||
{{Out}} |
|||
<pre> |
|||
$ zig test binomial.zig |
|||
All 1 tests passed. |
|||
</pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using 64 bit ints: |
Using 64 bit ints: |
||
< |
<syntaxhighlight lang="zkl">fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,528: | Line 3,183: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
{{trans|BBC_BASIC}} |
{{trans|BBC_BASIC}} |
||
< |
<syntaxhighlight lang="zxbasic">10 LET n=33: LET k=17: PRINT "Binomial ";n;",";k;" = "; |
||
20 LET r=1: LET d=n-k |
20 LET r=1: LET d=n-k |
||
30 IF d>k THEN LET k=d: LET d=n-k |
30 IF d>k THEN LET k=d: LET d=n-k |
||
Line 2,537: | Line 3,192: | ||
80 GO TO 40 |
80 GO TO 40 |
||
90 PRINT r |
90 PRINT r |
||
100 DEF FN m(a,b)=a-INT (a/b)*b</ |
100 DEF FN m(a,b)=a-INT (a/b)*b</syntaxhighlight> |
Latest revision as of 08:48, 23 July 2024
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
11l
F binomial_coeff(n, k)
V result = 1
L(i) 1..k
result = result * (n - i + 1) / i
R result
print(binomial_coeff(5, 3))
- Output:
10
360 Assembly
Very compact version.
* Evaluate binomial coefficients - 29/09/2015
BINOMIAL CSECT
USING BINOMIAL,R15 set base register
SR R4,R4 clear for mult and div
LA R5,1 r=1
LA R7,1 i=1
L R8,N m=n
LOOP LR R4,R7 do while i<=k
C R4,K i<=k
BH LOOPEND if not then exit while
MR R4,R8 r*m
DR R4,R7 r=r*m/i
LA R7,1(R7) i=i+1
BCTR R8,0 m=m-1
B LOOP loop while
LOOPEND XDECO R5,PG edit r
XPRNT PG,12 print r
XR R15,R15 set return code
BR R14 return to caller
N DC F'10' <== input value
K DC F'4' <== input value
PG DS CL12 buffer
YREGS
END BINOMIAL
- Output:
210
ABAP
CLASS lcl_binom DEFINITION CREATE PUBLIC.
PUBLIC SECTION.
CLASS-METHODS:
calc
IMPORTING n TYPE i
k TYPE i
RETURNING VALUE(r_result) TYPE f.
ENDCLASS.
CLASS lcl_binom IMPLEMENTATION.
METHOD calc.
r_result = 1.
DATA(i) = 1.
DATA(m) = n.
WHILE i <= k.
r_result = r_result * m / i.
i = i + 1.
m = m - 1.
ENDWHILE.
ENDMETHOD.
ENDCLASS.
- Output:
lcl_binom=>calc( n = 5 k = 3 ) 1,0000000000000000E+01 lcl_binom=>calc( n = 60 k = 30 ) 1,1826458156486142E+17
ACL2
(defun fac (n)
(if (zp n)
1
(* n (fac (1- n)))))
(defun binom (n k)
(/ (fac n) (* (fac (- n k)) (fac k)))
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;
- 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.
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))
)
- Output:
+10
ALGOL W
begin
% calculates n!/k! %
integer procedure factorialOverFactorial( integer value n, k ) ;
if k > n then 0
else if k = n then 1
else % k < n % begin
integer f;
f := 1;
for i := k + 1 until n do f := f * i;
f
end factorialOverFactorial ;
% calculates n! %
integer procedure factorial( integer value n ) ;
begin
integer f;
f := 1;
for i := 2 until n do f := f * i;
f
end factorial ;
% calculates the binomial coefficient of (n k) %
% uses the factorialOverFactorial procedure for a slight optimisation %
integer procedure binomialCoefficient( integer value n, k ) ;
if ( n - k ) > k
then factorialOverFactorial( n, n - k ) div factorial( k )
else factorialOverFactorial( n, k ) div factorial( n - k );
% display the binomial coefficient of (5 3) %
write( binomialCoefficient( 5, 3 ) )
end.
APL
When the factorial operator ! is used as a dyad, it returns the binomial coefficient: k!n = n choose k.
3!5
10
AppleScript
Imperative
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
Functional
Using a little more abstraction for readability, and currying for ease of both re-use and refactoring:
-- factorial :: Int -> Int
on factorial(n)
product(enumFromTo(1, n))
end factorial
-- binomialCoefficient :: Int -> Int -> Int
on binomialCoefficient(n, k)
factorial(n) div (factorial(n - k) * (factorial(k)))
end binomialCoefficient
-- Or, by reduction:
-- binomialCoefficient2 :: Int -> Int -> Int
on binomialCoefficient2(n, k)
product(enumFromTo(1 + k, n)) div (factorial(n - k))
end binomialCoefficient2
-- TEST -----------------------------------------------------
on run
{binomialCoefficient(5, 3), binomialCoefficient2(5, 3)}
--> {10, 10}
end run
-- GENERAL -------------------------------------------------
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
return lst
else
return {}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- product :: [Num] -> Num
on product(xs)
script multiply
on |λ|(a, b)
a * b
end |λ|
end script
foldl(multiply, 1, xs)
end product
- Output:
{10, 10}
Arturo
factorial: function [n]-> product 1..n
binomial: function [x,y]-> (factorial x) / (factorial y) * factorial x-y
print binomial 5 3
- Output:
10
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
}
Message box shows:
10
AWK
# syntax: GAWK -f EVALUATE_BINOMIAL_COEFFICIENTS.AWK
BEGIN {
main(5,3)
main(100,2)
main(33,17)
exit(0)
}
function main(n,k, i,r) {
r = 1
for (i=1; i<k+1; i++) {
r *= (n - i + 1) / i
}
printf("%d %d = %d\n",n,k,r)
}
- Output:
5 3 = 10 100 2 = 4950 33 17 = 1166803110
Batch File
@echo off & setlocal
if "%~2"=="" ( echo Usage: %~nx0 n k && goto :EOF )
call :binom binom %~1 %~2
1>&2 set /P "=%~1 choose %~2 = "<NUL
echo %binom%
goto :EOF
:binom <var_to_set> <N> <K>
setlocal
set /a coeff=1, nk=%~2 - %~3 + 1
for /L %%I in (%nk%, 1, %~2) do set /a coeff *= %%I
for /L %%I in (1, 1, %~3) do set /a coeff /= %%I
endlocal && set "%~1=%coeff%"
goto :EOF
- Output:
> binom.bat 5 3 5 choose 3 = 10 > binom.bat 100 2 100 choose 2 = 4950
The string n choose k =
is output to stderr, while the result is echoed to stdout. This should allow capturing the result with a for /f
loop without needing to define tokens or delims.
But...
> binom.bat 33 17 33 choose 17 = 0 > binom.bat 15 10 15 choose 10 = -547
The Windows cmd console only handles 32-bit integers. If a factoral exceeds 2147483647 at any point, set /a
will choke and roll over to a negative value, giving unexpected results. Unfortunately, this is as good as it gets for pure batch.
BCPL
GET "libhdr"
LET choose(n, k) =
~(0 <= k <= n) -> 0,
2*k > n -> binomial(n, n - k),
binomial(n, k)
AND binomial(n, k) =
k = 0 -> 1,
binomial(n, k - 1) * (n - k + 1) / k
LET start() = VALOF {
LET n, k = ?, ?
LET argv = VEC 20
LET sz = ?
sz := rdargs("n/a/n/p,k/a/n/p", argv, 20)
UNLESS sz ~= 0 RESULTIS 1
n := !argv!0
k := !argv!1
writef("%d choose %d = %d *n", n, k, choose(n, k))
RESULTIS 0
}
- Output:
Note that with the /p flag to rdargs(), the system will prompt if we don't supply both arguments on the command line.
$ cintsys64 BCPL 64-bit Cintcode System (13 Jan 2020) 0.004> nCk 50 25 50 choose 25 = 126410606437752 0.003> nCk 10 5 10 choose 5 = 252 0.004> nCk 100 2 100 choose 2 = 4950 0.000> nCk 100 98 100 choose 98 = 4950 0.004> nCk n > 5 k > 3 5 choose 3 = 10
BBC BASIC
@%=&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%
- Output:
Binomial (5,3) = 10 Binomial (100,2) = 4950 Binomial (33,17) = 1166803110
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
Burlesque
blsq ) 5 3nr
10
C
#include <stdio.h>
#include <limits.h>
/* We go to some effort to handle overflow situations */
static unsigned long gcd_ui(unsigned long x, unsigned long y) {
unsigned long t;
if (y < x) { t = x; x = y; y = t; }
while (y > 0) {
t = y; y = x % y; x = t; /* y1 <- x0 % y0 ; x1 <- y0 */
}
return x;
}
unsigned long binomial(unsigned long n, unsigned long k) {
unsigned long d, g, r = 1;
if (k == 0) return 1;
if (k == 1) return n;
if (k >= n) return (k == n);
if (k > n/2) k = n-k;
for (d = 1; d <= k; d++) {
if (r >= ULONG_MAX/n) { /* Possible overflow */
unsigned long nr, dr; /* reduced numerator / denominator */
g = gcd_ui(n, d); nr = n/g; dr = d/g;
g = gcd_ui(r, dr); r = r/g; dr = dr/g;
if (r >= ULONG_MAX/nr) return 0; /* Unavoidable overflow */
r *= nr;
r /= dr;
n--;
} else {
r *= n--;
r /= d;
}
}
return r;
}
int main() {
printf("%lu\n", binomial(5, 3));
printf("%lu\n", binomial(40, 19));
printf("%lu\n", binomial(67, 31));
return 0;
}
- Output:
10 131282408400 11923179284862717872
C#
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;
}
}
}
C++
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 binomialCoefficient(double n, double k)
{
if (abs(n - k) < 1e-7 || k < 1e-7) return 1.0;
if( abs(k-1.0) < 1e-7 || abs(k - (n-1)) < 1e-7)return n;
return Factorial(n) /(Factorial(k)*Factorial((n - k)));
}
Implementation:
int main()
{
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< binomialCoefficient(5,3);
cin.get();
}
- Output:
The Binomial Coefficient of 5, and 3, is equal to: 10
Clojure
(defn binomial-coefficient [n k]
(let [rprod (fn [a b] (reduce * (range a (inc b))))]
(/ (rprod (- n k -1) n) (rprod 1 k))))
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)}"
- Output:
> 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
Commodore BASIC
10 REM BINOMIAL COEFFICIENTS
20 REM COMMODORE BASIC 2.0
30 REM 2021-08-24
40 REM BY ALVALONGO
100 Z=0:U=1
110 FOR N=U TO 10
120 PRINT N;
130 FOR K=Z TO N
140 GOSUB 900
150 PRINT C;
160 NEXT K
170 PRINT
180 NEXT N
190 END
900 REM BINOMIAL COEFFICIENT
910 IF K<Z OR K>N THEN C=Z:RETURN
920 IF K=Z OR K=N THEN C=U:RETURN
930 P=K:IF N-K<P THEN P=N-K
940 C=U
950 FOR I=Z TO P-U
960 C=C/(I+U)*(N-I)
980 NEXT I
990 RETURN
Common 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))))
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));
}
- Output:
( 5 3) = 2 (100 2) = 50 (100 98) = 50 (100 50) = 1976664223067613962806675336
The above wouldn't work for me (100C50 correctly gives 100891344545564193334812497256).
T BinomialCoeff(T)(in T n, in T k)
{
T nn = n, kk = k, c = cast(T)1;
if (kk > nn - kk) kk = nn - kk;
for (T i = cast(T)0; i < kk; i++)
{
c = c * (nn - i);
c = c / (i + cast(T)1);
}
return c;
}
void main()
{
import std.stdio, std.bigint;
BinomialCoeff(10UL, 3UL).writeln;
BinomialCoeff(100.BigInt, 50.BigInt).writeln;
}
- Output:
120 100891344545564193334812497256
dc
[sx1q]sz[d0=zd1-lfx*]sf[skdlfxrlk-lfxlklfx*/]sb
Demonstration:
5 3lbxp
10
Annotated version:
[ 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
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.
EasyLang
func binomial n k .
if k > n / 2
k = n - k
.
numer = 1
for i = n downto n - k + 1
numer = numer * i
.
denom = 1
for i = 1 to k
denom = denom * i
.
return numer / denom
.
print binomial 5 3
Elixir
defmodule RC do
def choose(n,k) when is_integer(n) and is_integer(k) and n>=0 and k>=0 and n>=k do
if k==0, do: 1, else: choose(n,k,1,1)
end
def choose(n,k,k,acc), do: div(acc * (n-k+1), k)
def choose(n,k,i,acc), do: choose(n, k, i+1, div(acc * (n-i+1), i))
end
IO.inspect RC.choose(5,3)
IO.inspect RC.choose(60,30)
- Output:
10 118264581564861424
Erlang
choose(N, 0) -> 1;
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).
ERRE
PROGRAM BINOMIAL
!$DOUBLE
PROCEDURE BINOMIAL(N,K->BIN)
LOCAL R,D
R=1 D=N-K
IF D>K THEN K=D D=N-K END IF
WHILE N>K DO
R*=N
N-=1
WHILE D>1 AND (R-D*INT(R/D))=0 DO
R/=D
D-=1
END WHILE
END WHILE
BIN=R
END PROCEDURE
BEGIN
BINOMIAL(5,3->BIN)
PRINT("Binomial (5,3) = ";BIN)
BINOMIAL(100,2->BIN)
PRINT("Binomial (100,2) = ";BIN)
BINOMIAL(33,17->BIN)
PRINT("Binomial (33,17) = ";BIN)
END PROGRAM
- Output:
Binomial (5,3) = 10 Binomial (100,2) = 4950 Binomial (33,17) = 1166803110
F#
let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k]
Factor
: fact ( n -- n-factorial )
dup 0 = [ drop 1 ] [ dup 1 - fact * ] if ;
: choose ( n k -- n-choose-k )
2dup - [ fact ] tri@ * / ;
! outputs 10
5 3 choose .
! alternative using folds
USE: math.ranges
! (product [n..k+1] / product [n-k..1])
: choose-fold ( n k -- n-choose-k )
2dup 1 + [a,b] product -rot - 1 [a,b] product / ;
Fermat
The binomial function is built in.
Bin(5,3)
- Output:
10
Forth
: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;
5 3 choose . \ 10
33 17 choose . \ 1166803110
Fortran
Direct Method
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
- Output:
10
Avoiding Overflow
Of course this method doesn't avoid overflow completely just delays it. It could be extended by adding more entries to the primes array
program binomial
integer :: i, j
do j=1,20
write(*,fmt='(i2,a)',advance='no') j,'Cr = '
do i=0,j
write(*,fmt='(i0,a)',advance='no') n_C_r(j,i),' '
end do
write(*,'(a,i0)') ' 60C30 = ',n_C_r(60,30)
end do
stop
contains
pure function n_C_r(n, r) result(bin)
integer(16) :: bin
integer, intent(in) :: n
integer, intent(in) :: r
integer(16) :: num
integer(16) :: den
integer :: i
integer :: k
integer, parameter :: primes(*) = [2,3,5,7,11,13,17,19]
num = 1
den = 1
do i=0,r-1
num = num*(n-i)
den = den*(i+1)
if (i > 0) then
! Divide out common prime factors
do k=1,size(primes)
if (mod(i,primes(k)) == 0) then
num = num/primes(k)
den = den/primes(k)
end if
end do
end if
end do
bin = num/den
end function n_C_r
end program binomial
- Output:
1Cr = 1 1 2Cr = 1 2 1 3Cr = 1 3 3 1 4Cr = 1 4 6 4 1 5Cr = 1 5 10 10 5 1 6Cr = 1 6 15 20 15 6 1 7Cr = 1 7 21 35 35 21 7 1 8Cr = 1 8 28 56 70 56 28 8 1 9Cr = 1 9 36 84 126 126 84 36 9 1 10Cr = 1 10 45 120 210 252 210 120 45 10 1 11Cr = 1 11 55 165 330 462 462 330 165 55 11 1 12Cr = 1 12 66 220 495 792 924 792 495 220 66 12 1 13Cr = 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 14Cr = 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 15Cr = 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 16Cr = 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 17Cr = 1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 18Cr = 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 19Cr = 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 20Cr = 1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1 21Cr = 1 21 210 1330 5985 20349 54264 116280 203490 293930 352716 352716 293930 203490 116280 54264 20349 5985 1330 210 21 1 22Cr = 1 22 231 1540 7315 26334 74613 170544 319770 497420 646646 705432 646646 497420 319770 170544 74613 26334 7315 1540 231 22 1 23Cr = 1 23 253 1771 8855 33649 100947 245157 490314 817190 1144066 1352078 1352078 1144066 817190 490314 245157 100947 33649 8855 1771 253 23 1 24Cr = 1 24 276 2024 10626 42504 134596 346104 735471 1307504 1961256 2496144 2704156 2496144 1961256 1307504 735471 346104 134596 42504 10626 2024 276 24 1 25Cr = 1 25 300 2300 12650 53130 177100 480700 1081575 2042975 3268760 4457400 5200300 5200300 4457400 3268760 2042975 1081575 480700 177100 53130 12650 2300 300 25 1 60C30 = 118264581564861424
FreeBASIC
' FB 1.05.0 Win64
Function factorial(n As Integer) As Integer
If n < 1 Then Return 1
Dim product As Integer = 1
For i As Integer = 2 To n
product *= i
Next
Return Product
End Function
Function binomial(n As Integer, k As Integer) As Integer
If n < 0 OrElse k < 0 OrElse n <= k Then Return 1
Dim product As Integer = 1
For i As Integer = n - k + 1 To n
Product *= i
Next
Return product \ factorial(k)
End Function
For n As Integer = 0 To 14
For k As Integer = 0 To n
Print Using "####"; binomial(n, k);
Print" ";
Next k
Print
Next n
Print
Print "Press any key to quit"
Sleep
- 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
Frink
Frink has a built-in efficient function to find binomial coefficients. It produces arbitrarily-large integers.
println[binomial[5,3]]
FunL
FunL has pre-defined function choose
in module integers
, which is defined as:
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) )
- Output:
10 118264581564861424
Here it is defined using the recommended formula for this task.
import integers.factorial
def
binomial( n, k ) | k < 0 or k > n = 0
binomial( n, k ) = factorial( n )/factorial( n - k )/factorial( k )
GAP
# Built-in
Binomial(5, 3);
# 10
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))
}
- Output:
10 118264581564861424
Golfscript
Actually evaluating n!/(k! (n-k)!):
;5 3 # Set up demo input
{),(;{*}*}:f; # Define a factorial function
.f@.f@/\@-f/
But Golfscript is meant for golfing, and it's shorter to calculate :
;5 3 # Set up demo input
1\,@{1$-@\*\)/}+/
Groovy
Solution:
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))
}
Test:
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)
- Output:
10
GW-BASIC
10 REM BINOMIAL CALCULATOR
20 INPUT "N? ", N
30 INPUT "P? ", P
40 GOSUB 70
50 PRINT C
60 END
70 C = 0
80 IF N < 0 OR P<0 OR P > N THEN RETURN
90 IF P < N\2 THEN P = N - P
100 C = 1
110 FOR I = N TO P+1 STEP -1
120 C=C*I
130 NEXT I
140 FOR I = 1 TO N-P
150 C=C/I
160 NEXT I
170 RETURN
Haskell
The only trick here is realizing that everything's going to divide nicely, so we can use div instead of (/).
choose :: (Integral a) => a -> a -> a
choose n k = product [k+1..n] `div` product [1..n-k]
> 5 `choose` 3
10
Or, generate the binomial coefficients iteratively to avoid computing with big numbers:
choose :: (Integral a) => a -> a -> a
choose n k = foldl (\z i -> (z * (n-i+1)) `div` i) 1 [1..k]
Or using "caching":
coeffs = iterate next [1]
where
next ns = zipWith (+) (0:ns) $ ns ++ [0]
main = print $ coeffs !! 5 !! 3
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
Icon and Unicon
- Output:
choose(5,3)=10
math provides binocoef and factors provides factorial.
IS-BASIC
100 PROGRAM "Binomial.bas"
110 PRINT "Binomial (5,3) =";BINOMIAL(5,3)
120 DEF BINOMIAL(N,K)
130 LET R=1:LET D=N-K
140 IF D>K THEN LET K=D:LET D=N-K
150 DO WHILE N>K
160 LET R=R*N:LET N=N-1
170 DO WHILE D>1 AND MOD(R,D)=0
180 LET R=R/D:LET D=D-1
190 LOOP
200 LOOP
210 LET BINOMIAL=R
220 END DEF
J
Solution:
The dyadic form of the primitive !
([Out of]) evaluates binomial coefficients directly.
Example usage:
3 ! 5
10
Java
public class Binomial {
// precise, but may overflow and then produce completely incorrect results
private static long binomialInt(int n, int k) {
if (k > n - k)
k = n - k;
long binom = 1;
for (int i = 1; i <= k; i++)
binom = binom * (n + 1 - i) / i;
return binom;
}
// same as above, but with overflow check
private static Object binomialIntReliable(int n, int k) {
if (k > n - k)
k = n - k;
long binom = 1;
for (int i = 1; i <= k; i++) {
try {
binom = Math.multiplyExact(binom, n + 1 - i) / i;
} catch (ArithmeticException e) {
return "overflow";
}
}
return binom;
}
// using floating point arithmetic, larger numbers can be calculated,
// but with reduced precision
private static double binomialFloat(int n, int k) {
if (k > n - k)
k = n - k;
double binom = 1.0;
for (int i = 1; i <= k; i++)
binom = binom * (n + 1 - i) / i;
return binom;
}
// slow, hard to read, but precise
private static BigInteger binomialBigInt(int n, int k) {
if (k > n - k)
k = n - k;
BigInteger binom = BigInteger.ONE;
for (int i = 1; i <= k; i++) {
binom = binom.multiply(BigInteger.valueOf(n + 1 - i));
binom = binom.divide(BigInteger.valueOf(i));
}
return binom;
}
private static void demo(int n, int k) {
List<Object> data = Arrays.asList(
n,
k,
binomialInt(n, k),
binomialIntReliable(n, k),
binomialFloat(n, k),
binomialBigInt(n, k));
System.out.println(data.stream().map(Object::toString).collect(Collectors.joining("\t")));
}
public static void main(String[] args) {
demo(5, 3);
demo(1000, 300);
}
}
- Output:
5 3 10 10 10.0 10 1000 300 -8357011479171942 overflow 5.428250046406143E263 542825004640614064815358503892902599588060075560435179852301016412253602009800031872232761420804306539976220810204913677796961128392686442868524741815732892024613137013599170443939815681313827516308854820419235457578544489551749630302863689773725905288736148678480
Recursive version, without overflow check:
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));
}
}
- Output:
10
JavaScript
function binom(n, k) {
var coeff = 1;
var i;
if (k < 0 || k > n) return 0;
for (i = 0; i < k; i++) {
coeff = coeff * (n - i) / (i + 1);
}
return coeff;
}
console.log(binom(5, 3));
- Output:
10
jq
# nCk assuming n >= k
def binomial(n; k):
if k > n / 2 then binomial(n; n-k)
else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
end;
def task:
.[0] as $n | .[1] as $k
| "\($n) C \($k) = \(binomial( $n; $k) )";
;
([5,3], [100,2], [ 33,17]) | task
- Output:
5 C 3 = 10 100 C 2 = 4950 33 C 17 = 1166803110
Julia
Built-in
@show binomial(5, 3)
Recursive version:
function binom(n::Integer, k::Integer)
n ≥ k || return 0 # short circuit base cases
(n == 1 || k == 0) && return 1
n * binom(n - 1, k - 1) ÷ k
end
@show binom(5, 3)
- Output:
binomial(5, 3) = 10 binom(5, 3) = 10
K
{[n;k]_(*/(k-1)_1+!n)%(*/1+!k)} . 5 3
10
Alternative version:
{[n;k]i:!(k-1);_*/((n-i)%(i+1))} . 5 3
10
Using Pascal's triangle:
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
Kotlin
// version 2.0
fun binomial(n: Int, k: Int) = when {
n < 0 || k < 0 -> throw IllegalArgumentException("negative numbers not allowed")
n == k -> 1L
else -> {
val kReduced = min(k, n - k) // minimize number of steps
var result = 1L
var numerator = n
var denominator = 1
while (denominator <= kReduced)
result = result * numerator-- / denominator++
result
}
}
fun main(args: Array<String>) {
for (n in 0..14) {
for (k in 0..n)
print("%4d ".format(binomial(n, k)))
println()
}
}
- 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
Lambdatalk
{def C
{lambda {:n :p}
{/ {* {S.serie :n {- :n :p -1} -1}}
{* {S.serie :p 1 -1}}}}}
-> C
{C 16 8}
-> 12870
1{S.map {lambda {:n} {br}1
{S.map {C :n} {S.serie 1 {- :n 1}}} 1}
{S.serie 2 16}}
->
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
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)
- Output:
10 5 118264581564861424
Liberty BASIC
' [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
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
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
Additive recursion with memoization by hashing 2 input integer. Lua 5.3 support bit-wise operation; assume 64 bit integer implementation here.
local Binomial = setmetatable({},{
__call = function(self,n,k)
local hash = (n<<32) | (k & 0xffffffff)
local ans = self[hash]
if not ans then
if n<0 or k>n then
return 0 -- not save
elseif n<=1 or k==0 or k==n then
ans = 1
else
if 2*k > n then
ans = self(n, n - k)
else
local lhs = self(n-1,k)
local rhs = self(n-1,k-1)
local sum = lhs + rhs
if sum<0 or not math.tointeger(sum)then
-- switch to double
ans = lhs/1.0 + rhs/1.0 -- approximate
else
ans = sum
end
end
end
rawset(self,hash,ans)
end
return ans
end
})
print( Binomial(100,50)) -- 1.0089134454556e+029
Maple
convert(binomial(n,k),factorial);
binomial(5,3);
- Output:
factorial(n) ----------------------------- factorial(k) factorial(n - k) 10
Mathematica / Wolfram Language
(Local) In[1]:= Binomial[5,3]
(Local) Out[1]= 10
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:
>> nchoosek(5,3)
ans =
10
Alternative implementations are:
function r = binomcoeff1(n,k)
r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n
r = r(k);
end;
function r = binomcoeff2(n,k)
prod((n-k+1:n)./(1:k))
end;
function r = binomcoeff3(n,k)
m = pascal(max(n-k,k)+1);
r = m(n-k+1,k+1);
end;
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:
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
Sample Usage:
>> 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
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)) */
min
((dup 0 ==) 'succ (dup pred) '* linrec) :fact
('dup dip dup ((fact) () (- fact) (fact * div)) spread) :binomial
5 3 binomial puts!
- Output:
10
MINIL
// Number of combinations nCr
00 0E Go: ENT R0 // n
01 1E ENT R1 // r
02 2C CLR R2
03 2A Loop: ADD1 R2
04 0D DEC R0
05 1D DEC R1
06 C3 JNZ Loop
07 3C CLR R3 // for result
08 3A ADD1 R3
09 0A Next: ADD1 R0
0A 1A ADD1 R1
0B 50 R5 = R0
0C 5D DEC R5
0D 63 R6 = R3
0E 46 Mult: R4 = R6
0F 3A Add: ADD1 R3
10 4D DEC R4
11 CF JNZ Add
12 5D DEC R5
13 CE JNZ Mult
14 61 Divide:R6 = R1
15 5A ADD1 R5
16 3D Sub: DEC R3
17 9B JZ Exact
18 6D DEC R6
19 D6 JNZ Sub
1A 94 JZ Divide
1B 35 Exact: R3 = R5
1C 2D DEC R2
1D C9 JNZ Next
1E 03 R0 = R3
1F 80 JZ Go // Display result
This uses the recursive definition:
ncr(n, r) = 1 if r = 0
ncr(n, r) = n/r * ncr(n-1, r-1) otherwise
which results from the definition of ncr in terms of factorials.
МК-61/52
П1 <-> П0 ПП 22 П2 ИП1 ПП 22 П3
ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3
/ С/П ВП П0 1 ИП0 * L0 25 В/О
Input: n ^ k В/О С/П.
Nanoquery
def binomialCoeff(n, k)
result = 1
for i in range(1, k)
result = result * (n-i+1) / i
end
return result
end
if main
println binomialCoeff(5,3)
end
Nim
Note that a function to compute these coefficients, named “binom”, is available in standard module “math”.
proc binomialCoeff(n, k: int): int =
result = 1
for i in 1..k:
result = result * (n-i+1) div i
echo binomialCoeff(5, 3)
- Output:
10
Oberon-2
MODULE Binomial;
IMPORT
Out;
PROCEDURE For*(n,k: LONGINT): LONGINT;
VAR
i,m,r: LONGINT;
BEGIN
ASSERT(n > k);
r := 1;
IF k > n DIV 2 THEN m := n - k ELSE m := k END;
FOR i := 1 TO m DO
r := r * (n - m + i) DIV i
END;
RETURN r
END For;
BEGIN
Out.Int(For(5,2),0);Out.Ln
END Binomial.
- Output:
10
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.
Alternate version using big integers
#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)
;;
Simple recursive version
open Num;;
let rec binomial n k = if n = k then Int 1 else ((binomial (n-1) k) */ Int n) // Int (n-k)
Oforth
: binomial(n, k) | i | 1 k loop: i [ n i - 1+ * i / ] ;
- Output:
>5 3 binomial . 10
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}}
PARI/GP
binomial(5,3)
Pascal
See Delphi
Perl
sub binomial {
use bigint;
my ($r, $n, $k) = (1, @_);
for (1 .. $k) { $r *= $n--; $r /= $_ }
$r;
}
print binomial(5, 3);
- Output:
10
Since the bigint module already has a binomial method, this could also be written as:
sub binomial {
use bigint;
my($n,$k) = @_;
(0+$n)->bnok($k);
}
For better performance, especially with large inputs, one can also use something like:
use ntheory qw/binomial/;
print length(binomial(100000,50000)), "\n";
- Output:
30101
The Math::Pari module also has binomial, but it needs large amounts of added stack space for large arguments (this is due to using a very old version of the underlying Pari library).
Phix
There is a builtin choose() function which does this. From builtins/factorial.e (an autoinclude):
global function choose(integer n, k) atom res = 1 for i=1 to k do res = (res*(n-i+1))/i end for return res end function
Example:
?choose(5,3)
- Output:
10
However errors will creep in should any result or interim value exceed 9,007,199,254,740,992 (on 32-bit), so:
with javascript_semantics include builtins\mpfr.e sequence tests = {{5,3},{100,50},{60,30},{1200,120}} mpz r = mpz_init() for i=1 to length(tests) do integer {n,k} = tests[i] mpz_bin_uiui(r,n,k) ?mpz_get_str(r) end for
- Output:
"10" "100891344545564193334812497256" "118264581564861424" "1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600"
Note that I have re-implemented mpz_bin_uiui() mainly for the benefit of pwa/p2js, and some tweaks may be in order (please ask if needed) to match gmp proper for -ve n.
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;
?>
Alternative version, not based on factorial
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;
}
Picat
Iterative
binomial_it(N,K) = Res =>
if K < 0 ; K > N then
R = 0
else
R = 1,
foreach(I in 0..K-1)
R := R * (N-I) // (I+1)
end
end,
Res = R.
Using built-in factorial/1
binomial_fac(N,K) = factorial(N) // factorial(K) // factorial(N-K).
Recursion (tabled)
table
binomial_rec(_N, 0) = 1.
binomial_rec(0, _K) = 0.
binomial_rec(N, K) = binomial_rec(N-1,K-1) + binomial_rec(N-1,K).
Test
go =>
Tests = [[10,3],[60,30],[100,50],[400,200]],
foreach([N,K] in Tests)
println([N,K,binomial_it(N,K)])
end,
nl.
All methods prints the same result.
- Output:
[10,3,120] [60,30,118264581564861424] [100,50,100891344545564193334812497256] [400,200,102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120]
binomial_rec/2 is a little slower than the two other (0.036s vs 0.002s on these tests).
PicoLisp
(de binomial (N K)
(let f
'((N)
(if (=0 N) 1 (apply * (range 1 N))) )
(/
(f N)
(* (f (- N K)) (f K)) ) ) )
- Output:
: (binomial 5 3) -> 10
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;
- Output:
10
PowerShell
function choose($n,$k) {
if($k -le $n -and 0 -le $k) {
$numerator = $denominator = 1
0..($k-1) | foreach{
$numerator *= ($n-$_)
$denominator *= ($_ + 1)
}
$numerator/$denominator
} else {
"$k is greater than $n or lower than 0"
}
}
choose 5 3
choose 2 1
choose 10 10
choose 10 2
choose 10 8
Output:
10 2 1 45 45
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
Example
Enter value n: 5 Enter value k: 3 C(n,k)= 10
Python
Imperative
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))
- Output:
10
Functional
from operator import mul
from functools import reduce
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:
# r = n-r for smaller intermediate values during computation
return ( reduce( mul, range((n - (n-r) + 1), n + 1), 1)
// reduce( mul, range(1, (n-r) + 1), 1) )
else:
return ( reduce( mul, range((n - r + 1), n + 1), 1)
// reduce( mul, range(1, r + 1), 1) )
Or, abstracting a little more for legibility and ease of reuse, while currying for ease of mapping and general composition:
'''Evaluation of binomial coefficients'''
from functools import reduce
# binomialCoefficient :: Int -> Int -> Int
def binomialCoefficient(n):
'''n choose k, expressed in terms of
product and factorial functions.
'''
return lambda k: product(
enumFromTo(1 + k)(n)
) // factorial(n - k)
# TEST ----------------------------------------------------
# main :: IO()
def main():
'''Tests'''
print(
binomialCoefficient(5)(3)
)
# k=0 to k=5, where n=5
print(
list(map(
binomialCoefficient(5),
enumFromTo(0)(5)
))
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# factorial :: Int -> Int
def factorial(x):
'''The factorial of x, where
x is a positive integer.
'''
return product(enumFromTo(1)(x))
# product :: [Num] -> Num
def product(xs):
'''The product of a list of
numeric values.
'''
return reduce(lambda a, b: a * b, xs, 1)
# TESTS ---------------------------------------------------
if __name__ == '__main__':
main()
- Output:
10 [1, 5, 10, 10, 5, 1]
Compare the use of Python comments, (above); with the use of Python type hints, (below).
from typing import (Callable, List, Any)
from functools import reduce
from operator import mul
def binomialCoefficient(n: int) -> Callable[[int], int]:
return lambda k: product(enumFromTo(1 + k)(n)) // factorial(n - k)
def enumFromTo(m: int) -> Callable[[int], List[Any]]:
return lambda n: list(range(m, 1 + n))
def factorial(x: int) -> int:
return product(enumFromTo(1)(x))
def product(xs: List[Any]) -> int:
return reduce(mul, xs, 1)
if __name__ == '__main__':
print(binomialCoefficient(5)(3))
# k=0 to k=5, where n=5
print(list(map(binomialCoefficient(5), enumFromTo(0)(5))))
- Output:
10 [1, 5, 10, 10, 5, 1]
Quackery
[ tuck - over
1 swap times
[ over i + 1+ * ]
nip swap times
[ i 1+ / ] ] is binomial ( n n --> )
5 3 binomial echo
- Output:
10
R
R's built-in choose() function evaluates binomial coefficients:
choose(5,3)
- Output:
[1] 10
Racket
#lang racket
(require math)
(binomial 10 5)
Raku
(formerly Perl 6) For a start, you can get the length of the corresponding list of combinations:
say combinations(5, 3).elems;
- Output:
10
This method is efficient, as Raku will not actually compute each element of the list, since it actually uses an iterator with a defined count-only method. Such method performs computations in a way similar to the following infix operator:
sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. $^p }
say 5 choose 3;
A possible optimization would use a symmetry property of the binomial coefficient:
sub infix:<choose> { [*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p) }
One drawback of this method is that it returns a Rat, not an Int. So we actually may want to enforce the conversion:
sub infix:<choose> { ([*] ($^n ... 0) Z/ 1 .. min($n - $^p, $p)).Int }
And this is exactly what the count-only method does.
REXX
The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits.
idiomatic
/*REXX program calculates binomial coefficients (also known as combinations). */
numeric digits 100000 /*be able to handle gihugeic numbers. */
parse arg n k . /*obtain N and K from the C.L. */
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb: procedure; parse arg x,y; return !(x) % (!(x-y) * !(y))
!: procedure; !=1; do j=2 to arg(1); !=!*j; end /*j*/; return !
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 need be calculated.
/*REXX program calculates binomial coefficients (also known as combinations). */
numeric digits 100000 /*be able to handle gihugeic numbers. */
parse arg n k . /*obtain N and K from the C.L. */
say 'combinations('n","k')=' comb(n,k) /*display the number of combinations. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
comb: procedure; parse arg x,y; return pfact(x-y+1, x) % pfact(2, y)
/*──────────────────────────────────────────────────────────────────────────────────────*/
pfact: procedure; !=1; do j=arg(1) to arg(2); !=!*j; end /*j*/; return !
output is identical to the 1st REXX version.
It is (around average) about ten times faster than the 1st version for 200,20
and 100,10
.
For 100,80
it is about 30% faster.
Ring
numer = 0
binomial(5,3)
see "(5,3) binomial = " + numer + nl
func binomial n, k
if k > n return nil ok
if k > n/2 k = n - k ok
numer = 1
for i = 1 to k
numer = numer * ( n - i + 1 ) / i
next
return numer
RPL
RPL has a COMB
instruction which returns the result directly. If a home-made function is preferred, there are many possibilities.
Using the recommended formula and the stack:
≪ - LAST ! SWAP ! SWAP ROT ! * / ≫ ‘CHOOS’ STO
Using the formula with local variables:
≪ → n k ≪ n ! n k - ! / k ! / ≫ ≫ ‘CHOOS’ STO
To avoid data overflow for high values of n, using the formula simplified by (n-k)! :
≪ → n k ≪ 1 n k - 1 + n FOR j j * NEXT k ! / ≫ ≫ ‘CHOOS’ STO
All the above functions are called the same way and return the same result:
5 3 CHOOS
- Output:
10
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)
result
10 118264581564861424
another implementation:
def c n, r
(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end
end
Ruby's Arrays have a combination method which result in a (lazy) enumerator. This Enumerator has a "size" method, which returns the size of the enumerator, or nil if it can’t be calculated lazily. (Since Ruby 2.0)
(1..60).to_a.combination(30).size #=> 118264581564861424
Run BASIC
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
- Output:
binomial (5,1) = 5 binomial (5,2) = 10 binomial (5,3) = 10 binomial (5,4) = 5 binomial (5,5) = 1
Rust
fn fact(n:u32) -> u64 {
let mut f:u64 = n as u64;
for i in 2..n {
f *= i as u64;
}
return f;
}
fn choose(n: u32, k: u32) -> u64 {
let mut num:u64 = n as u64;
for i in 1..k {
num *= (n-i) as u64;
}
return num / fact(k);
}
fn main() {
println!("{}", choose(5,3));
}
- Output:
10
Alternative version, using functional style:
fn choose(n:u64,k:u64)->u64 {
let factorial=|x| (1..=x).fold(1, |a, x| a * x);
factorial(n) / factorial(k) / factorial(n - k)
}
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)
}
- Output:
The Binomial Coefficient of 5 and 3 equals 10.
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:
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)))
}
- Output:
java Binomial 100 30 The Binomial Coefficient of 100 and 30 equals 29,372,339,821,610,944,823,963,760.
Using recursive formula C(n,k) = C(n-1,k-1) + C(n-1,k)
:
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))
- Output:
bico(5,3) = 10
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)
- Output:
10
Alternatively a recursive implementation can be constructed from Pascal's Triangle:
(define (pascal i j)
(cond ((= i 0) 1)
((= j 0) 1)
(else (+
(pascal (- i 1) j)
(pascal i (- j 1))))))
(define (choose n k)
(pascal (- n k) k)))
(display (choose 5 3))
(newline)
- Output:
10
Seed7
The infix operator ! computes the binomial coefficient. E.g.: 5 ! 3 evaluates to 10. The binomial coefficient operator works also for negative values of n. E.g.: (-6) ! 10 evaluates to 3003.
$ include "seed7_05.s7i";
const proc: main is func
local
var integer: n is 0;
var integer: k is 0;
begin
for n range 0 to 66 do
for k range 0 to n do
write(n ! k <& " ");
end for;
writeln;
end for;
end func;
- 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 1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1 1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1 1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1 ...
The library bigint.s7i contains a definition of the binomial coefficient operator ! for the type bigInteger:
const func bigInteger: (in bigInteger: n) ! (in var bigInteger: k) is func
result
var bigInteger: binom is 0_;
local
var bigInteger: numerator is 0_;
var bigInteger: denominator is 0_;
begin
if n >= 0_ and k > n >> 1 then
k := n - k;
end if;
if k < 0_ then
binom := 0_;
elsif k = 0_ then
binom := 1_;
else
binom := n;
numerator := pred(n);
denominator := 2_;
while denominator <= k do
binom *:= numerator;
binom := binom div denominator;
decr(numerator);
incr(denominator);
end while;
end if;
end func;
Original source [1].
SequenceL
Simplest Solution:
choose(n, k) := product(k + 1 ... n) / product(1 ... n - k);
Tail-Recursive solution to avoid arithmetic with large integers:
choose(n,k) := binomial(n, k, 1, 1);
binomial(n, k, i, result) :=
result when i > k else
binomial(n, k, i + 1, (result * (n - i + 1)) / i);
Sidef
Straightforward translation of the formula:
func binomial(n,k) {
n! / ((n-k)! * k!)
}
say binomial(400, 200)
Alternatively, by using the Number.nok() method:
say 400.nok(200)
Smalltalk
Having a small language but a big class library in my bag, we can write:
Transcript showCR: (5 binco:3).
Transcript showCR: (400 binco:200)
- Output:
10 102952500135414432972975880320401986757210925381077648234849059575923332372651958598336595518976492951564048597506774120
A naïve implementation (in the Integer class) might look like:
binco:arg
^ (self factorial) / (arg factorial * (self-arg) factorial)
Standard ML
fun binomial n k =
if k > n then 0 else
let fun f (_, 0) = 1
| f (i, d) = f (i + 1, d - 1) * i div d
in f (n - k + 1, k) end
Stata
Use the comb function. Notice the result is a missing value if k>n or k<0.
. display comb(5,3)
10
Swift
func factorial<T: BinaryInteger>(_ n: T) -> T {
guard n != 0 else {
return 1
}
return stride(from: n, to: 0, by: -1).reduce(1, *)
}
func binomial<T: BinaryInteger>(_ x: (n: T, k: T)) -> T {
let nFac = factorial(x.n)
let kFac = factorial(x.k)
return nFac / (factorial(x.n - x.k) * kFac)
}
print("binomial(\(5), \(3)) = \(binomial((5, 3)))")
print("binomial(\(20), \(11)) = \(binomial((20, 11)))")
- Output:
binomial(5, 3) = 10 binomial(20, 11) = 167960
Tcl
This uses exact arbitrary precision integer arithmetic.
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}]
}
Demonstrating:
puts "5_C_3 = [binom 5 3]"
puts "60_C_30 = [binom 60 30]"
- Output:
5_C_3 = 10 60_C_30 = 118264581564861424
TI-57
Machine code | Comment |
---|---|
Lbl 9 STO 2 x⮂t STO 1 SBR 0 STO 3 RCL 1 - RCL 2 = SBR 0 INV Prd 3 RCL 2 SBR 0 Inv Prd 3 RCL 3 R/S RST Lbl 0 C.t x=t 1 STO 0 Lbl 1 RCL 0 × Dsz GTO 1 1 = INV SBR |
program binomial(x,t) // x is the display register r2 = x swap x and t r1 = x x = factorial(x) r3 = x x = r1 - r2 x = factorial(x) r3 /= x x = r2 x = factorial(x) r3 /= x x = r3 end program reset pointer program factorial(x) t=0 if x=0 then x=1 r0 = x loop multiply r0 by what will be in the next loop decrement r0 and exit loop if r0 = 0 end loop complete the multiplication sequence return x! end sub |
5
x⮂t
3
GTO
9
R/S
- Output:
10.
TI-83 BASIC
Builtin operator nCr gives the number of combinations.
10 nCr 4
- Output:
210
TI-89 BASIC
Builtin function.
nCr(n,k)
TXR
nCk is a built-in function, along with the one for permutations, nPk:
$ txr -p '(n-choose-k 20 15)'
15504
$ txr -p '(n-perm-k 20 15)'
20274183401472000
UNIX Shell
#!/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"
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.
#import nat
choose = ~&ar^?\1! quotient^\~&ar product^/~&al ^|R/~& predecessor~~
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.
choose = quotient^/factorial@l product+ factorial^~/difference ~&r
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.
choose("n","k") = quotient(factorial "n",product factorial~~ (difference("n","k"),"k"))
test program:
#cast %nL
main = choose* <(5,3),(60,30)>
- Output:
<10,118264581564861424>
VBScript
Function binomial(n,k)
binomial = factorial(n)/(factorial(n-k)*factorial(k))
End Function
Function factorial(n)
If n = 0 Then
factorial = 1
Else
For i = n To 1 Step -1
If i = n Then
factorial = n
Else
factorial = factorial * i
End If
Next
End If
End Function
'calling the function
WScript.StdOut.Write "the binomial coefficient of 5 and 3 = " & binomial(5,3)
WScript.StdOut.WriteLine
- Output:
the binomial coefficient of 5 and 3 = 10
Wren
import "./fmt" for Fmt
import "./math" for Int
var binomial = Fn.new { |n, k|
if (n < 0 || k < 0) Fiber.abort("Arguments must be non-negative integers")
if (n < k) Fiber.abort("The second argument cannot be more than the first.")
if (n == k) return 1
var prod = 1
var i = n - k + 1
while (i <= n) {
prod = prod * i
i = i + 1
}
return prod / Int.factorial(k)
}
var limit = 14
System.write("n/k |")
for (k in 0..limit) System.write(Fmt.d(5, k))
System.print()
System.write("----+" + "-----" * (limit + 1))
System.print()
for (n in 0..limit) {
System.write("%(Fmt.d(3, n)) |")
for (k in 0..n) System.write(Fmt.d(5, binomial.call(n, k)))
System.print()
}
- Output:
n/k | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ----+--------------------------------------------------------------------------- 0 | 1 1 | 1 1 2 | 1 2 1 3 | 1 3 3 1 4 | 1 4 6 4 1 5 | 1 5 10 10 5 1 6 | 1 6 15 20 15 6 1 7 | 1 7 21 35 35 21 7 1 8 | 1 8 28 56 70 56 28 8 1 9 | 1 9 36 84 126 126 84 36 9 1 10 | 1 10 45 120 210 252 210 120 45 10 1 11 | 1 11 55 165 330 462 462 330 165 55 11 1 12 | 1 12 66 220 495 792 924 792 495 220 66 12 1 13 | 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 14 | 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
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!
- 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
Zig
A reasonable implementation for a fixed word size is to precompute all possible values of nCk, since even on a 64 bit machine there's only 67 rows of Pascal's triangle to consider, or ~18K of data.
In Zig it's possible to compute all values of nCk at compile time, so that at runtime it's only necessary to do a table lookup. Zig also supports nullable values, so nCk can return a null value if the programmer requests a value that's out of range. Finally, since this code uses addition to compute the table, all entries that can fit in 64 bits can be computed, in contrast to some other code examples that may overflow before the maximum representable value (67 choose 33) is reached. For example, the largest value the BCPL version can compute is 61 choose 31.
const std = @import("std");
pub fn binomial(n: u32) ?[]const u64 {
if (n >= rmax)
return null
else {
const k = n * (n + 1) / 2;
return pascal[k .. k + n + 1];
}
}
pub fn nCk(n: u32, k: u32) ?u64 {
if (n >= rmax)
return null
else if (k > n)
return 0
else {
const j = n * (n + 1) / 2;
return pascal[j + k];
}
}
const rmax = 68;
const pascal = build: {
@setEvalBranchQuota(100_000);
var coefficients: [(rmax * (rmax + 1)) / 2]u64 = undefined;
coefficients[0] = 1;
var j: u32 = 0;
var k: u32 = 1;
var n: u32 = 1;
while (n < rmax) : (n += 1) {
var prev = coefficients[j .. j + n];
var next = coefficients[k .. k + n + 1];
next[0] = 1;
var i: u32 = 1;
while (i < n) : (i += 1)
next[i] = prev[i] + prev[i - 1];
next[i] = 1;
j = k;
k += n + 1;
}
break :build coefficients;
};
test "n choose k" {
const expect = std.testing.expect;
try expect(nCk(10, 5).? == 252);
try expect(nCk(10, 11).? == 0);
try expect(nCk(10, 10).? == 1);
try expect(nCk(67, 33).? == 14226520737620288370);
try expect(nCk(68, 34) == null);
}
Rather than write driver code, it's possible to run the unit test for this module.
- Output:
$ zig test binomial.zig All 1 tests passed.
zkl
Using 64 bit ints:
fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) }
- Output:
zkl: binomial(5,3) 10 zkl: binomial(60,30) 118264581564861424
ZX Spectrum Basic
10 LET n=33: LET k=17: PRINT "Binomial ";n;",";k;" = ";
20 LET r=1: LET d=n-k
30 IF d>k THEN LET k=d: LET d=n-k
40 IF n<=k THEN GO TO 90
50 LET r=r*n
60 LET n=n-1
70 IF (d>1) AND (FN m(r,d)=0) THEN LET r=r/d: LET d=d-1: GO TO 70
80 GO TO 40
90 PRINT r
100 DEF FN m(a,b)=a-INT (a/b)*b
- Programming Tasks
- Mathematical operations
- 11l
- 360 Assembly
- ABAP
- ACL2
- Ada
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- Batch File
- BCPL
- BBC BASIC
- Bracmat
- Burlesque
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Commodore BASIC
- Common Lisp
- D
- Dc
- Delphi
- EasyLang
- Elixir
- Erlang
- ERRE
- F Sharp
- Factor
- Fermat
- Forth
- Fortran
- FreeBASIC
- Frink
- FunL
- GAP
- Go
- Golfscript
- Groovy
- GW-BASIC
- Haskell
- HicEst
- Icon
- Unicon
- Icon Programming Library
- IS-BASIC
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- Lambdatalk
- Lasso
- Liberty BASIC
- Logo
- Lua
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Maxima
- Min
- MINIL
- МК-61/52
- Nanoquery
- Nim
- Oberon-2
- OCaml
- Oforth
- Oz
- PARI/GP
- Pascal
- Perl
- Ntheory
- Phix
- Phix/mpfr
- PHP
- Picat
- PicoLisp
- PL/I
- PowerShell
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Run BASIC
- Rust
- Scala
- Scheme
- Seed7
- SequenceL
- Sidef
- Smalltalk
- Standard ML
- Stata
- Swift
- Tcl
- TI-57
- TI-83 BASIC
- TI-89 BASIC
- TXR
- UNIX Shell
- Ursala
- VBScript
- Wren
- Wren-fmt
- Wren-math
- XPL0
- Zig
- Zkl
- ZX Spectrum Basic
- Pages with too many expensive parser function calls