Wednesday, March 08, 2006

Binomial Coefficient

Introduction

Binomial Coefficient, nCr = n! / ((n - r)! * r!).

Discussion

This code was derived from algorithms after Manolopoulos (2002) and User Contributed Notes (2006).

package math;

public final class Main {

    /**
     * Don't let anyone instantiate this class.
     */
    private Main() {
    }
    
    public static long binomialCoefficient(int n, int r) {
        long t = 1;
        
        int m = n - r; // r = Math.max(r, n - r);
        if (r < m) {
            r = m;
        }
        
        for (int i = n, j = 1; i > r; i--, j++) {
            t = t * i / j;
        }
        
        return t;
    }
    
    public static void main(String[] args) {
        // possible combinations of cards in a poker hand
        System.out.println(binomialCoefficient(52, 5)); // 2598960
        
        // possible combinations of numbers in lottery
        System.out.println(binomialCoefficient(49, 6)); // 13983816
    }
}

References

Author Manolopoulos, Yannis
Year 2002
Title Binomial Coefficient Computation: Recursion or Iteration?
Publisher ACM SIGCSE Bulletin, Volume 34, Issue 4

Author User Contributed Notes
Year 2006
Title Mastering Algorithms with Perl (Owant). In: LXXII. Mathematical Functions
Publisher php
Retrieved March 8, 2006 from http://php.morva.net/manual/en/ref.math.php

No comments: