Algorithmus für die Berechnung der Binomial-Koeffizienten

Brauche ich eine Möglichkeit, die Berechnung der Kombinationen ohne running out of memory. Hier ist, was ich habe, so weit.

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

Habe ich es markiert wie C#, aber die Lösung sollte idealerweise-unabhängigen Sprache.

Diese zahlen werden als "Binomialkoeffizienten" und als ein sehr häufiges Objekt, die erschienen sind, bevor Sie in SO: stackoverflow.com/q/4256188/422353
Welche Kombination genau versuchst du? Ist es einfach nCk, oder ist es etwas anderes? Ich bin nur gefragt, weil dein Kommentar am Anfang sagt "nCk" aber Ihr code nicht direkt berechnen.
Ja, fügen Sie diese Zeile zu factorial(): if (n > 20) throw new OverflowException();
Es ist einfach nCk.

InformationsquelleAutor Nyx | 2012-10-19

algorithm c#combinatorics math

8
```
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);
    }
```
- Obwohl die original-Beitrag setzt sich danach sehnt, der Rückgabewert sollte wirklich ein double oder long double. Wie hast du die Berechnungen mit Doppelzimmer, es gibt wirklich keinen Sinn, Sie zu konvertieren zurück in eine längst, wie die Antwort ist nicht unbedingt 100% genaue. Auch er schränkt die Werte für n und k sogar noch mehr.
- Das klappt perfekt. Danke.
- dies ist keine gute Lösung. zum Beispiel, Kombination(52,5) zurückgeben sollte, 2598960, nicht 2598959. Daneben Dominus ist sehr viel besser.
- Dies ist eine schlechte Lösung. Betrachten Kombination(7,7), Kombination(10,10), die 1 sein soll, nicht null ist. Das ist noch schlimmer, als es liefert korrigieren 1 für die Kombination(1,1), Kombination(2,2) bis zu sieben, geben falsche Hoffnung. Dies ist obwiously verursacht durch das Gießen zu lange, und der Verlust der Genauigkeit für einige zahlen. Macht die Funktion doppelklicken und entfernen der cast wird dieses Problem zu lösen, aber die Präzision noch nicht optimal.
- Das wäre die beste Lösung, aber (wenn der lange Gießen entfernt und das Ergebnis als double), wenn die zahlen größer sind als paar tausenden ist, wie Mark Dominus Lösung überläuft dann.
InformationsquelleAutor Victor Mukherjee
17

Einer der besten Methoden für die Berechnung der binomial-Koeffizienten, die ich gesehen habe vorgeschlagen, ist durch Mark Dominus. Es ist viel weniger wahrscheinlich zu überlaufen mit größeren Werten für N und K als einige andere Methoden.
```
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;
}
```
- Da r ist stets nicht-negativ ist, besser zu nutzen, ulong, statt lange zu ermöglichen, größere Koeffizienten zu berechnen, ohne überlauf.
- Noch besser BigInteger aus dem System.Numerik. Zum Beispiel: GetBinCoeff(64,33) gibt 1 zurück.77E18 wenn umgesetzt mit BigInteger (die richtige Antwort), sondern 3.43E17 und -2.68E17, wenn umgesetzt wird, ulong und long bzw.
- In standard-C# - Verwendung, die vorzeichenlose Ganzzahlen sind reserviert für bit-Felder oder andere Besondere verwendet so tun Sie das nicht. Berechnungen werden immer dann ausgeführt, signiert. Aber natürlich, fühlen Sie sich frei zu verwenden, BigInteger, wenn nötig.
InformationsquelleAutor Bob Bryan

Hier ist eine Lösung, die sehr ähnlich zu dem Bob Byran, aber prüft zwei weitere Voraussetzungen, um die Geschwindigkeit des Codes.

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

Der check n == k sollte wohl nicht da sein. Es ist eine Optimierung für einen statistisch seltenen Fall.

InformationsquelleAutor Moop

3

Suchen Sie in Ihrer code, ist es kein Wunder, dass der Speicher ziemlich schnell. Ihre Methode divideFactorials ruft die Methode factorial und verwendet als argument den Unterschied "Zähler-Nenner". Dieser Unterschied ist sehr wahrscheinlich gehen zu werden sehr groß nach Ihren code und Sie werden stecken in einer sehr langen Schleife im faktoriellen Methode.

Wenn es wirklich nur darum, nCk (was ich vermute, weil Ihr Kommentar in deinem code), verwenden Sie einfach:
```
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);
}
```
Natürlich mit dieser Methode wird die Reichweite sehr schnell, weil eine lange nicht wirklich support sehr lange zahlen, also n und k muss kleiner sein als 20.

Angenommen, dass Sie tatsächlich die Arbeit mit sehr großen zahlen, die Sie nutzen könnten doubles anstelle der sich danach sehnt, als die Kräfte mehr und mehr an Bedeutung.

Edit:
Wenn Sie große zahlen konnte man auch mit Stirling ' s Formel:

Wie n groß wird ln(n!) -> n*ln(n) - n.

Setzt das in code:
```
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));
}
```
Ich nur vorschlagen, diese Antwort, wie Sie sagten, die Sprache unabhängig ist, ist der C# code wird nur verwendet, um vorzuführen. Seit Sie brauchen, um große zahlen für n und k für diese zu arbeiten, ich schlage vor, dies als einen Allgemeinen Weg für die Suche nach der binomial-Koeffizient für große Kombinationen.

Für Fälle wurden n und k sind beide kleiner als rund 200-300, sollten Sie die Antwort Victor Mukherjee vorgeschlagen, wie es genau ist.

Edit2:
Bearbeitet meinen ersten code.
- Ich habe versucht, aus Victor ' s Antwort auf die etwa 20 000 Iterationen und es lief perfekt. Allerdings habe ich run out of memory bei diesem Bereich. Wenn ich eine größere Reichweite, ich werde wahrscheinlich verwenden Sie diese. Danke für deine Antwort.
- Warum würden Sie aus dem Speicher? Es ist nicht rekursiv, und es gibt keine Datenstrukturen beteiligt.
- Du hast Recht. Ich erstelle mehrere Datenstrukturen auf jeder iteration. Ich denke, die Auswahl des Algorithmus nicht ändern, eine Sache, außer vielleicht die Zeit, die es braucht.
- In der 5. Zeile der zweiten Ausschnitt in der Mathematik.Log(Math.Abs(n-k)) gibt es ein problem, wenn n und k gleich sind, wird die -Unendlichkeit (Ergebnis von Log(0)) weitergibt, NaN.
InformationsquelleAutor phil13131
2

Nur zur Vervollständigung: die standard - C math-Bibliothek hat Implementierungen der beiden Γ und lnΓ (genannt tgamma und lgamma), wo

Γ(n) = (n-1)!

Die Bibliothek Berechnung ist zweifellos schneller und genauer als Fazit Logarithmen. Für viel mehr Informationen finden Sie unter Wikipedia und Mathworld.

InformationsquelleAutor rici

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.