Berechne den Wert von n wähle k

Question

Was ist die effizienteste Methode, um den Wert von n zu bewerten wähle k? Die rohe Kraft, die ich denke, wäre, n faktorielle/k Fakultät/(n-k) Fakultät zu finden.

Eine bessere Strategie könnte sein, dp gemäß dieser recursive formula zu verwenden. Gibt es eine andere bessere Methode, um n zu bewerten, wählen Sie k?

Answer 1

Sie konnten die Multiplikativ Formel für diesen Einsatz:

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

Answer 2

"Am effizientesten" ist eine schlechte Anfrage. Was versuchen Sie effizient zu machen? Der Stapel? Erinnerung? Geschwindigkeit? Insgesamt ist meine Meinung, dass die rekursive Methode am effizientesten ist, da sie nur Addition (eine billige Operation) verwendet und die Rekursion für die meisten Fälle nicht zu schlecht ist. Die Funktion ist:

nchoosek(n, k) 
{ 
    if(k==0) return 1; 
    if(n==0) return 0; 
    return nchoosek(n-1, k-1)+nchoosek(n-1,k); 
} 

Answer 3

Wenn Sie eine Lookup-Tabelle von factorials haben dann die Berechnung von C (n, k) wird sehr schnell sein.

Answer 4

Das Problem mit dem n!/k!(n-k)! Ansatz ist nicht so sehr die Kosten, da das Thema mit ! sehr schnell wachsenden, so daß auch für Werte von nCk, die im Rahmen von gut sind, sagen wir, 64-Bit-Integer, Zwischenberechnungen sind nicht. Wenn Sie nicht kainaw die rekursive Addition Ansatz wie könnten Sie die multiplikative Ansatz versuchen:

nCk == product(i=1..k) (n-(k-i))/i

wo product(i=1..k) das Produkt aller Begriffe bedeutet, wenn i die Werte 1,2,...,k nimmt.

Answer 5

Wahrscheinlich die einfachste Möglichkeit, Binomialkoeffizienten (n choose k) ohne Überlauf zu berechnen, ist Pascal-Dreieck zu verwenden. Keine Brüche oder Multiplikationen sind notwendig. (n choose k). Die nth Zeile und die kth Eingabe von Pascals Dreieck geben den Wert an.

Take a look at this page. Dies ist eine O(n^2) Operation mit nur Addition, die Sie mit dynamischer Programmierung lösen können. Es wird blitzschnell für jede Zahl, die in eine 64-Bit-Ganzzahl passen kann.

Answer 6

Wenn Sie viele Kombinationen wie folgt berechnen gehen, die sicher die beste Option ist Triangle Pascal Berechnung. Wie Sie bereits die rekursive Formel wissen, ich glaube, ich kann hier vorbei einige Code:

MAX_N = 100 
MAX_K = 100 

C = [[1] + [0]*MAX_K for i in range(MAX_N+1)] 

for i in range(1, MAX_N+1): 
    for j in range(1, MAX_K+1): 
     C[i][j] = C[i-1][j-1] + C[i-1][j]; 

print C[10][2] 
print C[10][8] 
print C[10][3] 

Answer 7

Hier ist meine Version, die lediglich in ganzen Zahlen arbeitet (mit k die Division immer erzeugt einen ganzzahligen Quotienten) und ist schnell bei O (k):

function choose(n, k) 
    if k == 0 return 1 
    return (n * choose(n - 1, k - 1))/k 

ich schrieb es rekursiv, weil es so einfach ist und hübsch, aber man könnte es zu einer iterativen Lösung verwandeln, wenn Sie möchten.

Answer 8

Der schnellste Weg ist wahrscheinlich, die Formel zu verwenden, und nicht pascals Dreieck. Lass uns anfangen, keine Multiplikationen zu machen, wenn wir wissen, dass wir später durch die gleiche Zahl teilen werden. Wenn k < n/2, haben wir k = n - k.Wir wissen, dass C (n, k) = C (n, n-k) Jetzt:

n!/(k! x (n-k)!) = (product of numbers between (k+1) and n)/(n-k)! 

Zumindest mit dieser Technik sind Sie nie durch eine Zahl dividiert, die Sie vor multiplizieren verwendet. Sie haben (n-k) Multiplikationen und (n-k) Divisionen.

Ich denke über einen Weg nach, alle Spaltungen zu vermeiden, indem wir GCDs zwischen den Zahlen finden, die wir multiplizieren müssen, und denen, die wir teilen müssen. Ich werde versuchen, später zu bearbeiten.