你会怎么写这个算法大组合中最紧凑的方式?

StackOverflow https://stackoverflow.com/questions/956542

题

组合的数量 k 的项目，可以从中检索 N 项目是通过如下所述的公式。

             N! 
c =  ___________________ 
       (k! * (N - k)!)

一个例子是多少组合 6 Balls 可以得出一个鼓的 48 Balls 在抽奖。

优化这个公式，运用最小O时间的复杂性

这个问题的灵感来自于新的WolframAlpha数学的动机和事实上，它可以计算非常大的组合非常迅速。例如和随后的讨论主题上的另一个论坛。

http://www97.wolframalpha.com/input/?i=20000000+Choose+15000000

我会发布一些信息/链接讨论后，一些人采取一刀在的解决方案。

任何的语言是可接受的。

有帮助吗？

解决方案

注意到WolframAlpha返回"小数近似".如果你不需要绝对精确，你可以做同样的事情，通过计算阶乘与 斯特林的逼近.

现在，斯特林的近似要求的评价(n/e)^正，e为基础的自然对数，这将是迄今为止最慢的操作。但是，这可以通过使用技术中概述 另一个计算器后.

如果你用双精密和复平方要实现的指数，运作将：

  • 3项评价的斯特林的近似，每一个都需要O(日志n)乘法和一个广场根本的评价。
  • 2乘法
  • 1司

操作的数量可能减少有点小聪明，但总的时间复杂性将是O(日志n)这种做法。漂亮的可以管理的。

编辑：还有必要大量的学术文献对这一专题，鉴于常见的这种计算。一个很好的大学图书馆可以帮你跟踪它.

EDIT2:还有，如指出的另一个回应，值将很容易的溢出一个双人间，如此一个浮点类型的具有非常精度扩展，将需要用于即使是适度大值k和n.

其他提示

蟒蛇： O(min[k,n-k]2)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

分析：

  • 尺寸的 p 和 q 将线性增长循环内，如果 n-i 和 1+i 可被认为具有恒的大小。
  • 每个乘法将然后也增加了线性。
  • 这笔款项的所有迭代变的算术系列 k.

我的结论： O(k2)

如果改写为使用浮点数，乘法将原子操作，但我们将失去大量的精确度。它甚至为溢出 choose(20000000, 15000000).(不是一个大的惊喜，因为结果将围绕0.2119620413×104884378.)

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

我解决它在数学：

Binomial[n, k]

曼，这很简单...

<强>的Python：在近似 0 （1）

使用Python小数执行计算的近似。因为它不使用任何外部环路和数字大小限制，我认为它会执行在 0 （1）。

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

示例：

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

任何更高，它将溢出。指数似乎限于40000000。

鉴于n和k值的合理数量，计算它们提前，并使用一个查找表。

这是用某种方式（你卸载计算）回避的问题，但它是如果你有确定大量值的有用的技术。

MATLAB:

  • 骗子的方式(使用建立在功能 NCHOOSEK): 13字，O(?)

    nchoosek(N,k)

  • 我的解决方案： 36字，O(min(k,N k))

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)

我知道这是一个非常古老的问题，但我一个解决这个问题挣扎了很长一段时间，直到我发现了一个很简单的一个用VB写的6和它移植到C＃后，这里是结果：

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

在最后的代码是如此简单，你不会相信它会工作，直到你运行它。

此外，href="http://www.vb-helper.com/howto_calculate_n_choose_k.html" rel="nofollow">原创文章的

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top