40

评估 n 选择 k 值的最有效方法是什么？我认为的蛮力方法是找到 n factorial / k factorial / (nk) factorial 。

更好的策略可能是根据这个递归公式使用 dp 。还有其他更好的方法来评估 n 选择 k 吗？

4

8 回答 8

48

这是我的版本，它纯粹以整数工作（除以 k 总是产生整数商）并且在 O(k) 时速度很快：

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

我递归地写了它，因为它是如此简单和漂亮，但如果你愿意，你可以将它转换为迭代解决方案。

于 2013-03-08T20:10:08.527 回答
38

您可以为此使用乘法公式：

在此处输入图像描述

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

于 2013-03-08T20:06:44.713 回答
7

计算二项式系数(n choose k)而不溢出的最简单方法可能是使用帕斯卡三角形。不需要分数或乘法。(n choose k). 帕斯卡三角形的nth行和kth条目给出了值。

看看这个页面。这是一个O(n^2)只有加法的操作，你可以用动态规划来解决。对于任何可以放入 64 位整数的数字来说，这将是闪电般的速度。

于 2013-03-08T20:02:36.933 回答
5

如果你要计算很多这样的组合，计算帕斯卡三角形肯定是最好的选择。正如您已经知道递归公式一样，我想我可以在这里传递一些代码：

MAX_N = 100
MAX_K = 100

C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]

for i in range(1, MAX_N+1):
    for j in range(1, MAX_K+1):
        C[i][j] = C[i-1][j-1] + C[i-1][j];

print C[10][2]
print C[10][8]
print C[10][3]
于 2013-03-08T20:08:10.067 回答
1

该n!/k!(n-k)!方法的问题与其说是成本问题，不如说是!快速增长的问题，因此，即使其值nCk在 64 位整数范围内，中间计算也不是。如果您不喜欢 kainaw 的递归加法方法，您可以尝试乘法方法：

nCk == product(i=1..k) (n-(k-i))/i

where表示取值product(i=1..k)时所有项的乘积。i1,2,...,k

于 2013-03-08T19:54:59.797 回答
1

最快的方法可能是使用公式，而不是帕斯卡三角形。当我们知道以后要除以相同的数字时，让我们开始不做乘法。如果 k < n/2，让我们有 k = n - k。我们知道 C(n,k) = C(n,nk) 现在：

n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!

至少使用这种技术，您永远不会除以以前用来相乘的数字。你有 (nk) 乘法和 (nk) 除法。

我正在考虑一种避免所有除法的方法，通过在我们必须相乘的数字和我们必须除的数字之间找到 GCD。我稍后会尝试编辑。

于 2013-03-08T20:20:23.520 回答
0

如果您有一个阶乘查找表，那么 C(n,k) 的计算将非常快。

于 2013-03-08T19:53:09.440 回答
-4

“最有效”是一个糟糕的要求。你想提高什么效率？堆栈？记忆？速度？总的来说，我认为递归方法是最有效的，因为它只使用加法（一种廉价的操作），并且对于大多数情况，递归不会太糟糕。功能是：

nchoosek(n, k)
{
    if(k==0) return 1;
    if(n==0) return 0;
    return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}
于 2013-03-08T19:45:52.260 回答