scala

Calculate binomial coefficient for large n in Scala


I was wondering in Scala, if there's any way of calculating the binomial coefficient, choose k from n, or the number of k-combinations from a set of n elements.
It seems that for n=1000 and k=35, we could face overflowing issue when calculating 35! in Scala even when using Long.
Thanks!


Solution

  • Use BigInt and BigDecimal when working with numbers that won't fit into Int/Long/Float/Double.

    def permutations(n: Int): BigInt =
      (1 to n).map(BigInt(_)).foldLeft(BigInt(1))(_ * _)
    
    def combinations(n: Int, k: Int): BigInt =
      permutations(n) / (permutations(k) * permutations(n - k))
    
    combinations(1000, 35)
    // res23: BigInt = 53007599712421378893801108296363791932591235151324218238066214600