बिनोमियल गुणांक की गणना के लिए एल्गोरिदम

Question

मुझे स्मृति से बाहर किए बिना संयोजनों की गणना करने का एक तरीका चाहिए। यहां तक ​​कि मेरे पास अभी तक क्या है।

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))); 
} 

मैंने इसे सी # के रूप में टैग किया है, लेकिन समाधान आदर्श रूप से भाषा स्वतंत्र होना चाहिए।

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

अपने कोड को देखते हुए, यह आश्चर्य की बात नहीं है कि आप बहुत मेमोरी से बाहर निकल जाएंगे। आपकी विधि divideFactorials विधि फ़ैक्टोरियल को कॉल करती है और "numerator-denominator" अंतर को तर्क के रूप में उपयोग करती है। यह अंतर आपके कोड के अनुसार बहुत बड़ा होने जा रहा है और आप अपने फैक्टोरियल विधि में बहुत लंबे लूप में फंस जाएंगे।

तो यह वास्तव में है बस NCK खोजने के बारे में (जो मुझे लगता है क्योंकि अपने कोड में अपनी टिप्पणी), बस का उपयोग करें:

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); 
} 

बेशक

इस प्रक्रिया में बहुत तेजी से सीमा से बाहर चला जाएगा का उपयोग कर, क्योंकि एक लंबे समय तक वास्तव में बहुत लंबी संख्या का समर्थन नहीं करता है, इसलिए एन और के को 20 से छोटा होना चाहिए।

मान लीजिए कि आप वास्तव में बहुत बड़ी संख्या के साथ काम करते हैं, आप लंबे समय के बजाय युगल का उपयोग कर सकते हैं, क्योंकि शक्तियां अधिक से अधिक महत्वपूर्ण हो जाती हैं।

संपादित करें: आप बड़ी संख्या का उपयोग करते हैं तो आप भी स्टर्लिंग के फॉर्मूला इस्तेमाल कर सकते हैं:

n के रूप में बड़े ln हो जाता है -> n * ln (एन) - एन (एन!)।

कोड में इस लाना:

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)); 
} 

के रूप में आप ने कहा कि स्वतंत्र भाषा, सी # कोड बस इसे प्रदर्शित करने के लिए प्रयोग किया जाता है मैं केवल इस उत्तर का प्रस्ताव। चूंकि आपको काम करने के लिए एन और के लिए बड़ी संख्याओं का उपयोग करने की आवश्यकता है, इसलिए मैं बड़े संयोजनों के लिए द्विपक्षीय गुणांक खोजने के लिए इसे सामान्य तरीके के रूप में प्रस्तावित करता हूं।

मामलों के लिए एन और के दोनों 200-300 से छोटे थे, तो आपको उत्तर विक्टर मुखर्जी का प्रस्ताव देना चाहिए, क्योंकि यह सही है।

संपादित 2: मेरा पहला कोड संपादित किया गया।

Answer 3

बस पूरा होने की खातिर

: मानक C गणित पुस्तकालय दोनों Γ और ln Γ (tgamma कहा जाता है और lgamma), के कार्यान्वयन है जहां

Γ (एन) और के बराबर होती है; (N-1)!

लाइब्रेरी गणना निश्चित रूप से तेजी से और तुलनात्मक लॉगरिदम से अधिक सटीक है। बहुत अधिक जानकारी के लिए, Wikipedia और Mathworld देखें।

Answer 4

मैंने देखा है कि द्विपक्षीय गुणांक की गणना के लिए सबसे अच्छी विधियों में से एक है Mark Dominus द्वारा। कुछ अन्य तरीकों से एन और के लिए बड़े मूल्यों के साथ बहने की संभावना बहुत कम है।

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

यहां एक समाधान है जो बॉब बायरन के समान है, लेकिन कोड को तेज़ करने के लिए दो और पूर्व शर्त जांचता है।

/// <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; 
    } 

ये संख्या