Thuật toán để tính hệ số nhị thức

Question

Tôi cần một cách tính kết hợp mà không cần hết bộ nhớ. Đây là những gì tôi có cho đến nay.

public static long combination(long n, long k) // nCk 
{ 
    return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k)))))); 
} 

public static long factorial(long n) 
{ 
    long result; 
    if (n <= 1) return 1; 
    result = factorial(n - 1) * n; 
    return result; 
} 

public static long divideFactorials(long numerator, long denominator) 
{ 
    return factorial(Math.Abs((numerator - denominator))); 
} 

Tôi đã gắn thẻ nó là C#, nhưng giải pháp lý tưởng nên là ngôn ngữ độc lập.

Answer 1

public static long combination(long n, long k) 
    { 
     double sum=0; 
     for(long i=0;i<k;i++) 
     { 
      sum+=Math.log10(n-i); 
      sum-=Math.log10(i+1); 
     } 
     return (long)Math.pow(10, sum); 
    } 

Answer 2

Nhìn vào mã của bạn, không có gì lạ khi bạn sẽ hết bộ nhớ khá nhanh. Phương thức của bạn divideFactorials gọi phương thức giai thừa và sử dụng làm đối số sự khác biệt "tử số-mẫu số". Sự khác biệt đó rất có thể sẽ rất lớn theo mã của bạn và bạn sẽ bị mắc kẹt trong một vòng lặp rất dài trong phương pháp giai thừa của bạn.

Nếu nó thực sự chỉ là về việc tìm kiếm NCK (mà tôi giả sử vì bình luận của bạn trong mã của bạn), chỉ cần sử dụng:

public static long GetnCk(long n, long k) 
{ 
    long bufferNum = 1; 
    long bufferDenom = 1; 

    for(long i = n; i > Math.Abs(n-k); i--) 
    { 
     bufferNum *= i; 
    } 

    for(long i = k; i => 1; i--) 
    { 
     bufferDenom *= i; 
    } 

    return (long)(bufferNom/bufferDenom); 
} 

Tất nhiên sử dụng phương pháp này, bạn sẽ chạy ra khỏi phạm vi rất nhanh, bởi vì một dài không thực sự hỗ trợ số rất dài, vì vậy n và k phải nhỏ hơn 20.

Giả sử bạn thực sự làm việc với số lượng rất lớn bạn có thể sử dụng tăng gấp đôi thay vì thời gian dài, vì quyền hạn ngày càng trở nên quan trọng.

Edit: Nếu bạn sử dụng một số lượng lớn bạn cũng có thể sử dụng công thức Stirling của:

Như n trở ln lớn -> n * ln (n) - n (n!).

Đưa này vào mã:

public static double GetnCk(long n, long k) 
{ 
    double buffern = n*Math.Log(n) - n; 
    double bufferk = k*Math.Log(k) - k; 
    double bufferkn = Math.Abs(n-k)*Math.Log(Math.Abs(n-k)) - Math.Abs(n-k); 

    return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn)); 
} 

tôi chỉ đề xuất câu trả lời này, như bạn nói ngôn ngữ độc lập, mã C# là chỉ được sử dụng để chứng minh điều đó. Vì bạn cần sử dụng số lớn cho n và k để làm việc này, tôi đề xuất đây là cách tổng quát để tìm hệ số nhị thức cho các kết hợp lớn.

Đối với các trường hợp là n và k nhỏ hơn khoảng 200-300, bạn nên sử dụng câu trả lời mà Victor Mukherjee đề xuất, vì nó chính xác.

Chỉnh sửa2: Đã chỉnh sửa mã đầu tiên của tôi.

Answer 3

Chỉ vì lợi ích hoàn thành: tiêu chuẩn C thư viện toán học có triển khai của cả hai Γ và ln Γ (gọi tắt là tgamma và lgamma), nơi

Γ (n) & tương đương; (n-1)!

Tính toán thư viện chắc chắn nhanh hơn và chính xác hơn so với tổng hợp logarit. Để biết thêm thông tin, hãy xem Wikipedia và Mathworld.

Answer 4

Một trong những phương pháp tốt nhất để tính hệ số nhị thức mà tôi đã thấy được đề xuất là Mark Dominus. Nó ít có khả năng tràn với giá trị lớn hơn cho N và K so với một số phương pháp khác.

public static long GetBinCoeff(long N, long K) 
{ 
    // This function gets the total number of unique combinations based upon N and K. 
    // N is the total number of items. 
    // K is the size of the group. 
    // Total number of unique combinations = N!/(K! (N - K)!). 
    // This function is less efficient, but is more likely to not overflow when N and K are large. 
    // Taken from: http://blog.plover.com/math/choose.html 
    // 
    long r = 1; 
    long d; 
    if (K > N) return 0; 
    for (d = 1; d <= K; d++) 
    { 
     r *= N--; 
     r /= d; 
    } 
    return r; 
} 

Answer 5

Đây là giải pháp rất giống với Bob Byran, nhưng kiểm tra thêm hai điều kiện tiên quyết để tăng tốc mã.

/// <summary> 
    /// Calculates the binomial coefficient (nCk) (N items, choose k) 
    /// </summary> 
    /// <param name="n">the number items</param> 
    /// <param name="k">the number to choose</param> 
    /// <returns>the binomial coefficient</returns> 
    public static long BinomCoefficient(long n, long k) 
    { 
     if (k > n) { return 0; } 
     if (n == k) { return 1; } // only one way to chose when n == k 
     if (k > n - k) { k = n - k; } // Everything is symmetric around n-k, so it is quicker to iterate over a smaller k than a larger one. 
     long c = 1; 
     for (long i = 1; i <= k; i++) 
     { 
      c *= n--; 
      c /= i; 
     } 
     return c; 
    }