哪种方法更好地计算nCr？

Question

方法一：
C(n,r) = n!/(n-r)!r!

方法二：
在书籍 《组合算法》(Combinatorial Algorithms) 作者Wilf 中，我发现了这个:
C(n,r)可以写成C(n-1,r) + C(n-1,r-1)。

例如：

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

正如您所看到的，最终解决方案不需要进行任何乘法计算。在每个C(n,r)形式中，要么n等于r，要么r等于1。

这是我实现的示例代码：

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

请参见这里的输出。

在第二种方法中，存在重叠子问题，我们需要递归调用来再次解决相同的子问题。我们可以使用动态规划来避免这个问题。

我想知道计算C(n,r)的更好方法是什么？

- Green goblin

---

如果 r 等于 1，就返回 n；你确定不想返回 1 吗？ - user529758

请查看此问题：高效计算组合和排列。 - ypercubeᵀᴹ

另外，https://dev59.com/6Gox5IYBdhLWcg3wQSAO#9331125 - Ben Voigt

添加以下代码：如果(r==0) return 1; 否则，该代码将在nc0上产生分段错误。 - kapil

请问，这个算法的复杂度是多少？ - Tushar Jain

Answer 1

两种方法都可以节省时间，但第一种方法很容易发生整数溢出。

方法 1：

该方法将在最短的时间内（至多 n/2 次迭代）生成结果，并且通过仔细地进行乘法运算，可以减少溢出的可能性：

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

这段代码将从较小的端口开始对分子进行乘法运算，由于任意k个连续整数的积都可以被k!整除，因此不会出现除法问题。但仍可能存在溢出的可能性，另一个有用的技巧是在进行乘法和除法之前将n-r+i和i除以它们的GCD（最大公约数）（仍然可能发生溢出）。

方法2：

在此方法中，您将实际上建立起帕斯卡三角形。动态方法比递归方法快得多（前者为O(n^2)，而后者则为指数级别）。但是，您还需要使用O(n^2)的内存。

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

然后你可以在O(1)时间内查找任何C(n, r)。如果您需要特定的C(n，r)（即不需要完整三角形），则可以通过从上到下覆盖同一行来将存储器消耗降至O(n)。

# define MAX 100
long long row[MAX + 1];

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

内部循环从结尾开始，以简化计算。如果你从索引0开始，你将需要另一个变量来存储正在被覆盖的值。

- Sufian Latif

---

如果你将 i 和 n-r+i 的最大公约数除掉，就可以先除后乘。这样，只有在结果溢出时才会发生溢出。 - Daniel Fischer

请问可以更详细地解释一下方法1吗？我不太明白“a”乘以“n-r+i”，然后再除以“i”的部分。 - toothie

@toothie 这个公式来自于组合数学中的排列组合公式：C(n, r) = n (n - 1) ... (n - r + i) ... (n - r + 1) / 1.2. ... .i. ... r 可以重写为 C(n, r) = (n / r) ((n - 1) / (r - 1)) ... ((n - r + i) / i) ... ((n - r + 1) / 1)。第一种方法是从最后一个开始相乘。 - Sufian Latif

@0605002 哦，现在明白了。谢谢。 - toothie

@0605002。我不明白为什么外层循环是i<n而不是i<=n。如果我没错的话，在每个i的迭代之后，row[j]将等于iCr。如果我错了，请澄清一下。谢谢。 - sathya_dev

Answer 2

我认为你的递归方法应该可以有效地与DP一起使用。但是一旦约束条件增加，它就会开始出现问题。请参见http://www.spoj.pl/problems/MARBLES/。

这里是我在在线评测和编程竞赛中使用的函数。所以它的运行速度非常快。

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

这是对你的第一种方法的高效实现。

- nims

---

你真的需要那三个条件吗？我猜第三个条件 ans=(ans*n)/j; 对于每次迭代来说已经足够了。而且我不明白你的方法如何防止整数溢出。ans*n 很可能会超出范围。 - Ankesh Anand

@AnkeshAnand 确实 ans=(ans*n)/j 可能会超出边界，但前两个条件是为了防止溢出而进行除法运算的情况。它们只是尝试计算那些由于溢出而无法通过 ans=(ans*n)/j 计算的极少数情况。 - nims

我懂了，如果问题的限制非常大，那么(ans*n)将会超出范围，而不管你的前两个检查条件如何。我目前正在使用最后一个条件，而且它在大量问题集上有效。 - Ankesh Anand

在没有先进行检查的情况下执行“ans = n/j”所导致的错误是“(ansn)%j”。我们能否想出一种计算方式，以避免临时结果溢出，而不用担心溢出问题？希望只需进行几次除法，因为它们速度较慢并且通常仅在管道中运行。 - Peter Cordes

63C29是错误的。正确的是：759510004936100355。 - Suraj Jain

Answer 3

您的递归方法很好，但是结合动态规划会减少解决子问题的开销。现在我们已经有了两个条件-

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

现在我们可以通过将子结果存储在二维数组中轻松构建DP解决方案-

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

现在如果您想进一步优化，获取二项式系数的质因数分解可能是最有效的计算方法，特别是如果乘法很昂贵。

我知道的最快方法是Vladimir's method。通过将nCr分解为质因数来避免所有除法。正如Vladimir所说，您可以使用Eratosthenes筛法相当有效地完成这项工作。还可以使用Fermat's little theorem计算nCr mod MOD（其中MOD是一个素数）。

- Varun Garg

---

这就是你所说的弗拉基米尔方法吗？这是唯一的版本吗？https://www.quora.com/What-are-some-efficient-algorithms-to-compute-nCr - Job

为了计算 ncr%m，我可以这样做吗：return dp[n][r] = (nCr(n-1,r)%m + nCr(n-1,r-1)%m)%m; - ajaysinghnegi

Answer 4

使用动态规划算法可以轻松地找到nCr的解决方案，以下是代码实现：

package com.practice.competitive.maths;

import java.util.Scanner;

public class NCR1 {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int testCase = scanner.nextInt();
            while (testCase-- > 0) {
                int n = scanner.nextInt();
                int r = scanner.nextInt();
                int[][] combination = combination();
                System.out.println(combination[n][r]%1000000007);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int[][] combination() {
        int combination[][] = new int[1001][1001];
        for (int i = 0; i < 1001; i++)
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    combination[i][j] = 1;
                else
                    combination[i][j] = combination[i - 1][j - 1] % 1000000007 + combination[i - 1][j] % 1000000007;
            }
        return combination;
    }
}

- Vpn_talent

Answer 5

unsigned long long ans = 1,a=1,b=1;
        int k = r,i=0;
        if (r > (n-r))
            k = n-r;
        for (i = n ; k >=1 ; k--,i--)
        {
            a *= i;
            b *= k;
            if (a%b == 0)
            {
                a = (a/b);
                b=1;
            }
        }
        ans = a/b;

- Ram