Wie würden Sie diesen Algorithmus für große Kombinationen in der kompakteste Weise schreiben?

https://stackoverflow.com/questions/956542

12-09-2019
|

Frage

Die Anzahl der Kombinationen von k Gegenstände, die aus N Artikel abgerufen werden kann, wird durch die folgende Formel beschrieben.

             N! 
c =  ___________________ 
       (k! * (N - k)!)

Ein Beispiel wäre, wie viele Kombinationen von 6 Balls aus einer Trommel 48 Balls in einer Verlosung gezogen werden.

Mit dieser Formel optimiert mit der kleinsten O Zeitkomplexität

laufen

Diese Frage wurde von der neuen Wolframalpha Mathematik-Engine inspiriert und der Tatsache, dass es sehr schnell sehr große Kombinationen berechnen kann. z.B. und eine anschließende Diskussion über das Thema auf einem anderen Forum.

http://www97.wolframalpha.com/input/?i = 20000000 + wählen + 15000000

Ich werde ein paar Infos / Links von dieser Diskussion veröffentlichen, nachdem einige Leute an der Lösung einen Stich nehmen.

Jede Sprache akzeptabel ist.

Lösung

Beachten Sie, dass eine Wolframalpha „Dezimalapproximation“ zurückgibt. Wenn Sie keine absolute Präzision benötigen, können Sie das gleiche tun, indem Sie die factorials Berechnung mit Stirling Approximation .

Nun erfordert Stirlings Annäherung der Bewertung von (n / e) ^ n, wobei e die Basis des natürlichen Logarithmus ist, der mit Abstand der langsamste Betrieb sein wird. Aber dies kann unter Verwendung der Techniken in umrissener erfolgen eine andere Stackoverflow Post .

Wenn Sie mit doppelter Genauigkeit verwenden und wiederholten Quadratur das Potenzierung zu erreichen, werden die Operationen sein:

3 Bewertungen eines Stirling Näherung jeweils erfordern O (log n) Multiplikationen und eine Quadratwurzel Auswertung.
2 Multiplikationen
1 Divisionen

Die Anzahl der Operationen wahrscheinlich mit ein wenig Klugheit reduziert werden könnte, aber die gesamte Zeitkomplexität sein wird, O (log n) mit diesem Ansatz. Ziemlich überschaubar.

EDIT: Es gibt auch viele wissenschaftliche Literatur zu diesem Thema gebunden zu sein, da, wie üblich diese Berechnung ist. Eine gute Universitätsbibliothek könnte Ihnen helfen, die Spur zu kommen.

EDIT2: Auch, wie in einer anderen Antwort darauf hingewiesen, werden die Werte überlaufen leicht ein Doppel, so ein Gleitkommatyps mit sehr erweiterter Präzision benötigt noch mäßig große Werte von k verwendet werden und n

Andere Tipps

Python: O (min [ k n - k ] ²)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

Analyse:

Die Größe der p und q wird linear innerhalb der Schleife zu erhöhen, wenn n-i und 1+i können in Betracht gezogen werden, um konstante Größe zu haben.
Die Kosten für jede Multiplikation wird dann erhöhen auch linear.
Diese Summe aller Iterationen wird eine arithmetische Reihe über k.

Mein Fazit: O (k ²)

Wenn neu geschrieben Gleitkommazahlen zu verwenden, werden die Multiplikationen atomare Operationen, aber wir werden eine Menge Präzision verlieren. Es überläuft sogar für choose(20000000, 15000000). (Keine große Überraschung, da das Ergebnis wäre um 0,2119620413 × 10 ^4884378).

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

Ich würde löse es in Mathematica :

Binomial[n, k]

Der Mensch, das war einfach ...

Python: Annäherung in O (1)

Mit Python dezimal Implementierung eine Annäherung zu berechnen. Da es keine externe Schleife verwenden ist, und die Zahlen in der Größe begrenzt, ich denke, es auszuführen in wird O (1).

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

Beispiel:

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

Jede höher, und es wird überlaufen. Der Exponent scheint 40000000 begrenzt werden.

eine angemessene Anzahl von Werten für n und K gegeben, berechnen sie im Voraus und eine Verweistabelle verwenden.

Es ist das Problem in irgendeiner Art und Weise ausweichen (Sie die Berechnung sind Offloading), aber es ist eine nützliche Technik, wenn Sie eine große Anzahl von Werten zu bestimmen haben.

MATLAB:

Die Cheater Weg (mit der integrierten Funktion
Ich weiß, dass dies eine wirklich alte Frage, aber ich kämpfte mit einer Lösung für dieses Problem für eine lange Zeit, bis ich eine wirklich einfache in VB geschrieben hat 6 und nachdem es auf C # zu portieren, hier ist das Ergebnis:
```
public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}
```
Der letzte Code ist so einfach, dass man nicht glauben, dass es funktionieren wird, bis Sie es ausführen.
Auch die rel="nofollow"> gibt einige schöne Erklärung, wie er den letzten Algorithmus erreicht .

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow