Binomial Coefficient "n Choose K", In Python - Programming Idioms

This language bar is your friend. Select your favorite languages! Select your favorite languages :

• C
• C++
• C#
• Go
• Java
• JS
• Obj-C
• PHP
• Python
• Ruby
• Rust
• Or search :

Idiom #67 Binomial coefficient "n choose k"

Calculate binom(n, k) = n! / (k! * (n-k)!). Use an integer type able to handle huge numbers.

• Definition in Wikipedia

• Python
• Python
• C
• Clojure
• C#
• D
• Dart
• Fortran
• Go
• Haskell
• JS
• Java
• PHP
• Pascal
• Perl
• Perl
• Ruby
• Rust

• Python

import math def binom(n, k): return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

• Demo
• Doc
• Origin

• Python

import math def binom(n, k): return math.comb(n, k)

• Demo
• Doc
• Origin

• C
• Clojure
• C#
• D
• Dart
• Fortran
• Go
• Haskell
• JS
• Java
• PHP
• Pascal
• Perl
• Perl
• Ruby
• Rust

long long binom(long long n, long long k){ long long outp = 1; for(long long i = n - k + 1; i <= n; ++i) outp *= i; for(long long i = 2; i <= k; ++i) outp /= i; return outp; } (defn binom [n k] (let [fact #(apply * (range 1 (inc %)))] (/ (fact n) (* (fact k) (fact (- n k)))))) System.Numerics public BigInteger binom(int n, int k) { return factorial(n)/(factorial(k) * factorial(n-k)); } public BigInteger factorial(int x) { BigInteger result = 1; for(int i=1;i<=x;i++) { result = result * i; } return result; } import std.bigint; BigInt binom(uint n, uint k) { assert(n >= k); BigInt r = 1; for(uint i = 0; i <= k; ++i) { r *= n-i; r /= i+1; } return r; } int binom(int n, int k) { int result = 1; for (int i = 0; i < k; i++) { result = result * (n - i) ~/ (i + 1); } return result; } integer, parameter :: i8 = selected_int_kind(18) integer, parameter :: dp = selected_real_kind(15) n = 100 k = 5 print *,nint(exp(log_gamma(n+1.0_dp)-log_gamma(n-k+1.0_dp)-log_gamma(k+1.0_dp)),kind=i8) import "math/big" z := new(big.Int) z.Binomial(n, k)

• Demo
• Doc

binom n k = product [1+n-k..n] `div` product [1..k] const fac = x => x ? x * fac (x - 1) : x + 1 const binom = (n, k) => fac (n) / fac (k) / fac (n - k >= 0 ? n - k : NaN) import java.math.BigInteger; static BigInteger binom(int N, int K) { BigInteger ret = BigInteger.ONE; for (int k = 0; k < K; k++) { ret = ret.multiply(BigInteger.valueOf(N-k)) .divide(BigInteger.valueOf(k+1)); } return ret; }

• Demo
• Origin

gmp_binomial($n, $k);

• Demo
• Doc

uses ncalc; var N, K, Res: TValue; begin Res := BinomN(N, K); end. sub binom { my ($n, $k) = @_; if ($k > $n - $k) { $k = $n - $k } my $r = 1; for ( my $i = $n/$n ; $i <= $k;) { $r *= $n-- / $i++ } return $r } use bigint; sub binom { my ($n, $k) = @_; my $fact = sub { my $n = shift; return $n<2 ? 1 : $n * $fact->($n-1); }; return $fact->($n) / ($fact->($k) * ($fact->($n-$k))); } def binom(n,k) (1+n-k..n).inject(:*)/(1..k).inject(:*) end extern crate num; use num::bigint::BigInt; use num::bigint::ToBigInt; use num::traits::One; fn binom(n: u64, k: u64) -> BigInt { let mut res = BigInt::one(); for i in 0..k { res = (res * (n - i).to_bigint().unwrap()) / (i + 1).to_bigint().unwrap(); } res }

• Demo

Do you know the best way to do this in your language ? New implementation... < > ⌨ Idiom created by programming-idioms.org History

• View revisions

Cheatsheets Issues

• Report a bug

×

Please choose a nickname before doing this

No security, no password. Other people might choose the same nickname.

OK

• Python

def binom(n, k): return math.factorial(n) // math.factorial(k) // math.factorial(n - k)

• Python

def binom(n, k): return math.comb(n, k)

• C

long long binom(long long n, long long k){ long long outp = 1; for(long long i = n - k + 1; i <= n; ++i) outp *= i; for(long long i = 2; i <= k; ++i) outp /= i; return outp; }

• Clojure

(defn binom [n k] (let [fact #(apply * (range 1 (inc %)))] (/ (fact n) (* (fact k) (fact (- n k))))))

• C#

public BigInteger binom(int n, int k) { return factorial(n)/(factorial(k) * factorial(n-k)); } public BigInteger factorial(int x) { BigInteger result = 1; for(int i=1;i<=x;i++) { result = result * i; } return result; }

• D

BigInt binom(uint n, uint k) { assert(n >= k); BigInt r = 1; for(uint i = 0; i <= k; ++i) { r *= n-i; r /= i+1; } return r; }

• Dart

int binom(int n, int k) { int result = 1; for (int i = 0; i < k; i++) { result = result * (n - i) ~/ (i + 1); } return result; }

• Fortran

integer, parameter :: i8 = selected_int_kind(18) integer, parameter :: dp = selected_real_kind(15) n = 100 k = 5 print *,nint(exp(log_gamma(n+1.0_dp)-log_gamma(n-k+1.0_dp)-log_gamma(k+1.0_dp)),kind=i8)

• Go

z := new(big.Int) z.Binomial(n, k)

• Haskell

binom n k = product [1+n-k..n] `div` product [1..k]

• JS

const fac = x => x ? x * fac (x - 1) : x + 1 const binom = (n, k) => fac (n) / fac (k) / fac (n - k >= 0 ? n - k : NaN)

• Java

static BigInteger binom(int N, int K) { BigInteger ret = BigInteger.ONE; for (int k = 0; k < K; k++) { ret = ret.multiply(BigInteger.valueOf(N-k)) .divide(BigInteger.valueOf(k+1)); } return ret; }

• PHP

gmp_binomial($n, $k);

• Pascal

var N, K, Res: TValue; begin Res := BinomN(N, K); end.

• Perl

sub binom { my ($n, $k) = @_; if ($k > $n - $k) { $k = $n - $k } my $r = 1; for ( my $i = $n/$n ; $i <= $k;) { $r *= $n-- / $i++ } return $r }

• Perl

sub binom { my ($n, $k) = @_; my $fact = sub { my $n = shift; return $n<2 ? 1 : $n * $fact->($n-1); }; return $fact->($n) / ($fact->($k) * ($fact->($n-$k))); }

• Ruby

def binom(n,k) (1+n-k..n).inject(:*)/(1..k).inject(:*) end

• Rust

fn binom(n: u64, k: u64) -> BigInt { let mut res = BigInt::one(); for i in 0..k { res = (res * (n - i).to_bigint().unwrap()) / (i + 1).to_bigint().unwrap(); } res }