在Scala中计算大n的二项式系数

qfe3c7zg  于 11个月前  发布在  Scala
关注(0)|答案(2)|浏览(107)

我想知道在Scala中,是否有任何方法可以计算二项式系数,从n中选择k,或者从一组n个元素中选择k个组合的数量。
对于n=1000k=35,即使使用Long,在Scala中计算35!时也可能会遇到溢出问题。
谢谢你,谢谢

cbeh67ev

cbeh67ev1#

使用BigIntBigDecimal处理不适合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

字符串

fumotvh3

fumotvh32#

你不需要计算大因子。
如果n >= k >= 1,则C(n,k)= C(n-1,k-1)* n / k
这个怎么样?

def choose(n:Int,k:Int):BigInt = {
      if (k == 1)
        BigInt(n)
      else if (n == k)
        BigInt(1)
      else if (k == 0)
        BigInt(1)
      else
        choose(n-1, k-1) * n / k
    }

字符串

相关问题