Evaluate binomial coefficients: Difference between revisions

This programming task, is to calculate ANY binomial coefficient.

 

 

This formula is recommended:

 

'''See Also:'''

* [[Pascal's triangle]]

{{Template:Combinations and permutations}}

 

(if (zp n)

1

 

(defun binom (n k)

 

=={{header|Ada}}==

with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Binomial is

end loop;

end Test_Binomial;

<pre>

1

{{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]}}

 

(

INT result;

test:(

print((choose(5, 3), new line))

<pre>

+10

</pre>

 

=={{header|AppleScript}}==

set k to 3

 

 

return n_factorial / (n_minus_k_factorial) * 1 / (k_factorial) as integer

=={{header|AutoHotkey}}==

 

;---------------------------------------------------------------------------

}

Return, r

Message box shows:

<pre>10</pre>

 

=={{header|BBC BASIC}}==

PRINT "Binomial (5,3) = "; FNbinomial(5, 3)

ENDWHILE

= R%

<pre>Binomial (5,3) = 10

Binomial (100,2) = 4950

 

=={{header|Bracmat}}==

n k coef

. !arg:(?n,?k)

binomial$(5,3)

10

 

=={{header|Burlesque}}==

 

blsq ) 5 3nr

10

 

=={{header|C}}==

#include <limits.h>

 

 

 

}

 

 

=={{header|C sharp|C#}}==

 

namespace BinomialCoefficients

}

}

 

=={{header|Clojure}}==

(let [rprod (fn [a b] (reduce * (range a (inc b))))]

 

=={{header|CoffeeScript}}==

binomial_coefficient = (n, k) ->

result = 1

for k in [0..n]

console.log "binomial_coefficient(#{n}, #{k}) = #{binomial_coefficient(n,k)}"

 

> coffee binomial.coffee

binomial_coefficient(5, 0) = 1

binomial_coefficient(5, 4) = 5

binomial_coefficient(5, 5) = 1

 

=={{header|Common Lisp}}==

(defun choose (n k)

(labels ((prod-enum (s e)

(fact (n) (prod-enum 1 n)))

(/ (prod-enum (- (1+ n) k) n) (fact k))))

 

=={{header|D}}==

if (k > (n / 2))

k = n - k;

writefln("(%3d %3d) = %s", d[0], d[1], binomial(d[0], d[1]));

writeln("(100 50) = ", binomial(100.BigInt, 50.BigInt));

{{out}}

<pre>( 5 3) = 2

(100 98) = 50

(100 50) = 1976664223067613962806675336</pre>

 

=={{header|dc}}==

 

Demonstration:

 

<tt>10</tt>

 

Annotated version:

 

[sx [ x is our dump register; get rid of extraneous copy of n we no longer need]sx

1 [ return value is 1 ]sx

] sb

 

 

=={{header|Delphi}}==

 

 

{$APPTYPE CONSOLE}

Writeln('C(5,3) is ', BinomialCoff(5, 3));

ReadLn;

 

=={{header|Erlang}}==

choose(N, K) when is_integer(N), is_integer(K), (N >= 0), (K >= 0), (N >= K) ->

choose(N, K, 1, 1).

choose(N, K, I, Acc) ->

choose(N, K, I+1, (Acc * (N-I+1)) div I).

 

=={{header|F Sharp|F#}}==

let choose n k = List.fold (fun s i -> s * (n-i+1)/i ) 1 [1..k]

 

=={{header|Forth}}==

 

5 3 choose . \ 10

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

implicit none

end function choose

 

 

=={{header|Frink}}==

println[binomial[5,3]]

 

=={{header|FunL}}==

FunL has pre-defined function <code>choose</code> in module <code>integers</code>, which is defined as:

choose( n, k ) | k < 0 or k > n = 0

choose( n, 0 ) = 1

 

println( choose(5, 3) )

{{out}}

<pre>

 

Here it is defined using the recommended formula for this task.

 

def

binomial( n, k ) | k < 0 or k > n = 0

 

=={{header|GAP}}==

Binomial(5, 3);

 

=={{header|Go}}==

import "fmt"

import "math/big"

fmt.Println(new(big.Int).Binomial(5, 3))

fmt.Println(new(big.Int).Binomial(60, 30))

{{out}}

<pre>

=={{header|Golfscript}}==

Actually evaluating n!/(k! (n-k)!):

{),(;{*}*}:f; # Define a factorial function

But Golfscript is meant for golfing, and it's shorter to calculate <math>\prod_{i=0}^{k-1} \frac{n-i}{i+1}</math>:

 

 

=={{header|Groovy}}==

Solution:

assert x > -1

x == 0 ? 1 : (1..x).inject(1G) { BigInteger product, BigInteger factor -> product *= factor }

assert n >= k

factorial(n).intdiv(factorial(k)*factorial(n-k))

 

Test:

assert combinations(20, 10) == (combinations(19, 9) + combinations(19, 10))

assert combinations(5, 3) == 10

 

<pre>10</pre>

 

=={{header|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]

 

 

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":

 

where

next ns = zipWith (+) (0:ns) $ ns ++ [0]

 

 

=={{header|HicEst}}==

 

FUNCTION factorial( n )

FUNCTION BinomCoeff( n, k )

BinomCoeff = factorial(n)/factorial(n-k)/factorial(k)

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

write("choose(5,3)=",binocoef(5,3))

<pre>choose(5,3)=10</pre>

 

[http://www.cs.arizona.edu/icon/library/src/procs/factors.icn factors provides factorial].

 

 

k := integer(k) | fail

return i

 

 

=={{header|J}}==

 

'''Example usage:'''

 

=={{header|Java}}==

}

 

}

 

}

}

 

public static void main(String[] args) {

}

 

 

{

private static long binom(int n, int k)

System.out.println(binom(5, 3));

}

<pre>10</pre>

 

=={{header|JavaScript}}==

var coeff = 1;

return coeff;

}

<pre>10</pre>

 

=={{header|K}}==

 

Alternative version:

 

Using Pascal's triangle:

pascal 5

(1

 

{[n;k](pascal n)[n;k]} . 5 3

 

 

 

=={{header|Lasso}}==

#k == 0 ? return 1

local(result = 1)

binomial(5, 3)

binomial(5, 4)

 

<pre>10

5

118264581564861424</pre>

 

=={{header|Liberty BASIC}}==

' [RC] Binomial Coefficients

 

end function

 

 

=={{header|Maple}}==

 

<pre> factorial(n)

-----------------------------

10</pre>

 

 

=={{header|MATLAB}} / {{header|Octave}}==

 

Solution:

ans =

 

Alternative implementations are:

 

r = diag(rot90(pascal(n+1))); % vector of all binomial coefficients for order n

r = r(k);

 

prod((n-k+1:n)./(1:k))

 

m = pascal(max(n-k,k)+1);

r = m(n-k+1,k+1);

 

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:

 

coefficients = zeros(numel(n),numel(k)); %Preallocate memory

end

Sample Usage:

 

ans =

ans =

 

 

=={{header|Maxima}}==

binomial(-5, 3); /* -35 */

binomial( 5, -3); /* 0 */

 

binomial(a, b); /* binomial(a, b) */

 

=={{header|МК-61/52}}==

ИП0 ИП1 - ПП 22 ИП3 * П3 ИП2 ИП3

 

''Input'': ''n'' ^ ''k'' В/О С/П.

 

=={{header|OCaml}}==

let binomialCoeff n p =

let p = if p < n -. p then p else n -. p in

else res in

cm 1. n 1.

=== Alternate version using big integers ===

open Num;;

 

else a (succ j) ((v */ (Int (n - j))) // (Int (succ j)))

in a 0 (Int 1)

 

=== Simple recursive version ===

 

=={{header|Oz}}==

{{trans|Python}}

fun {BinomialCoeff N K}

{List.foldL {List.number 1 K 1}

end

in

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

 

=={{header|Perl}}==

use bigint;

my ($r, $n, $k) = (1, @_);

$r;

}

 

{{out}}

<pre>10</pre>

 

 

{{out}}

 

=={{header|PL/I}}==

binomial_coefficients:

procedure options (main);

end fact;

end binomial_coefficients;

10

 

}

 

=={{header|PureBasic}}==

Protected Result=1

While n>0

Print("Press ENTER to quit"): Input()

CloseConsole()

'''Example

Enter value n: 5

 

=={{header|Python}}==

result = 1

for i in range(1, k+1):

 

if __name__ == "__main__":

<pre>10</pre>

 

def comb(n,r):

''' calculate nCr - the binomial coefficient

38760

'''

 

=={{header|R}}==

R's built-in choose() function evaluates binomial coefficients:

 

 

=={{header|Racket}}==

#lang racket

(require math)

(binomial 10 5)

 

=={{header|REXX}}==

The task is to compute ANY binomial coefficient(s), but these REXX examples are limited to 100k digits.

===idiomatic===

<pre>

combinations(5,3)= 10

</pre>

<pre>

combinations(1200,120)= 1004576581793084916475353119318331966507299414258370667602185866686463289093457468590558508056798211449853806741873396451735444387513582540860551330127062642417424083600

 

===optimized===

 

=={{header|Ruby}}==

 

{{works with|Ruby|1.8.7+}}

# binomial coefficient: n C k

def choose(k)

 

p 5.choose(3)

result

<pre>10

another implementation:

 

def c n, r

(0...r).inject(1) do |m,i| (m * (n - i)) / (i + 1) end

end

 

=={{header|Run BASIC}}==

print "binomial (5,2) = "; binomial(5, 2)

print "binomial (5,3) = "; binomial(5, 3)

next i

binomial = coeff

<pre>binomial (5,1) = 5

binomial (5,2) = 10

binomial (5,4) = 5

binomial (5,5) = 1</pre>

 

=={{header|Scala}}==

def main(args: Array[String]): Unit = {

val n=5

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)

 

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:

 

def binomialCoefficient(n: Int, k: Int) =

(BigInt(n - k + 1) to n).product /

val Array(n, k) = args.map(_.toInt)

println("The Binomial Coefficient of %d and %d equals %,3d.".format(n, k, binomialCoefficient(n, k)))

 

 

Using recursive formula <code>C(n,k) = C(n-1,k-1) + C(n-1,k)</code>:

case (n, 0) => 1

case (0, k) => 0

case (n, k) => bico(n - 1, k - 1) + bico(n - 1, k)

}

 

=={{header|Scheme}}==

{{Works with|Scheme|R<math>^5</math>RS}}

(define (*factorial n acc)

(if (zero? n)

 

(display (choose 5 3))

 

=={{header|Seed7}}==

 

result

local

begin

end while;

end if;

end func;

 

 

 

=={{header|Tcl}}==

This uses exact arbitrary precision integer arithmetic.

proc binom {n k} {

# Compute the top half of the division; this is n!/(n-k)!

# Integer arithmetic divide is correct here; the factors always cancel out

return [expr {$pTop / $pBottom}]

Demonstrating:

<pre>5_C_3 = 10

60_C_30 = 118264581564861424</pre>

 

=={{header|TI-89 BASIC}}==

Builtin function.

 

 

=={{header|TXR}}==

nCk is a built-in function, along with the one for permutations, nPk:

 

 

 

=={{header|UNIX Shell}}==

 

n=5;

k=3;

binomial_coefficient=$(expr $n_factorial \/ $k_factorial \* 1 \/ $n_minus_k_factorial )

 

 

=={{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.

 

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.

* 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.

* <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.

* 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.

test program:

 

<pre><10,118264581564861424></pre>

 

=={{header|XPL0}}==

 

func Binomial(N, K);

CrLf(0);

];

 

<pre>

1

</pre>

 

=={{header|zkl}}==

Using 64 bit ints:

{{out}}

<pre>

118264581564861424

</pre>