Algoritmo per il calcolo del coefficiente binomiale

Question

Ho bisogno di un modo per calcolare le combinazioni senza esaurire la memoria. Ecco cosa ho finora.

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

Ho etichettato come C#, ma la soluzione dovrebbe idealmente essere indipendente dalla lingua.

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

Guardando il codice, non c'è da meravigliarsi che si esaurirà la memoria abbastanza velocemente. Il tuo metodo divideFactorials chiama il metodo fattoriale e usa come argomento la differenza "numeratore-denominatore". Probabilmente questa differenza sarà molto grande in base al tuo codice e sarai bloccato in un ciclo molto lungo nel tuo metodo fattoriale.

Se è davvero solo di trovare NCK (che presumo perché il tuo commento nel codice), basta usare:

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

Naturalmente con questo metodo verrà eseguito fuori portata molto veloce, perché un long in realtà non supporta numeri molto lunghi, quindi n e k devono essere minori di 20.

Supponendo che si lavori effettivamente con numeri molto grandi, si possono usare doppi invece di lunghi, poiché i poteri diventano sempre più significativi.

Edit: Se si utilizza un gran numero si potrebbe anche usare la formula di Stirling:

Come n diventa grande ln -> n * ln (n) - n (n!).

Mettendo questo in codice:

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

propongo solo questa risposta, come hai detto linguaggio indipendente, il codice C# è solo utilizzato per dimostrarlo. Dal momento che è necessario utilizzare numeri grandi per n e k perché ciò funzioni, propongo questo come un modo generale per trovare il coefficiente binomiale per le combinazioni grandi.

Per i casi in cui n e k sono entrambi inferiori a circa 200-300, è necessario utilizzare la risposta che Victor Mukherjee ha proposto, in quanto è esatta.

Edit2: Modificato il mio primo codice.

Answer 3

Solo per il gusto di completamento: il C libreria matematica standard dispone di implementazioni di entrambi Γ e ln Γ (chiamato tgamma e lgamma), dove

Γ (n) e uguale; (N-1)!

Il calcolo della libreria è sicuramente più rapido e accurato della somma dei logaritmi. Per ulteriori informazioni, vedere Wikipedia e Mathworld.

Answer 4

Uno dei metodi migliori per calcolare il coefficiente binomiale che ho visto suggerito è il Mark Dominus. È molto meno probabile che trabocchi con valori più grandi per N e K rispetto ad altri metodi.

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

Ecco una soluzione molto simile a Bob Byran, ma controlla altre due precondizioni per accelerare il codice.

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