Calcolare il valore di n scegliere k

Question

Qual è il metodo più efficiente per valutare il valore di n scegliere k? Il modo di forza bruta che penso sarebbe quello di trovare fattoriale/k fattoriale/(n-k) fattoriale.

Una strategia migliore potrebbe essere l'utilizzo di dp in base a questo recursive formula. C'è qualche altro metodo migliore per valutare n scegliere k?

Answer 1

si potrebbe usare la formula moltiplicativo per questo:

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

Answer 2

"Più efficiente" è una richiesta scadente. Cosa stai cercando di rendere efficiente? Lo stack? Memoria? Velocità? Nel complesso, la mia opinione è che il metodo ricorsivo sia il più efficiente perché utilizza solo l'aggiunta (un'operazione a basso costo) e la ricorsione non sarà troppo negativa per la maggior parte dei casi. La funzione è:

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

Se si dispone di una tabella di ricerca dei fattoriali allora il calcolo di C (n, k) sarà molto veloce.

Answer 4

Il problema con l'approccio n!/k!(n-k)! non è tanto il costo come la questione con ! crescendo molto rapidamente in modo che, anche per valori di nCk che sono ben all'interno della portata, per esempio, interi a 64-bit, calcoli intermedi sono non. Se non vi piace l'approccio Inoltre ricorsivo di kainaw si potrebbe provare l'approccio moltiplicativo:

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

dove product(i=1..k) si intende il prodotto di tutti i termini quando i assume i valori 1,2,...,k.

Answer 5

Probabilmente il modo più semplice per calcolare i coefficienti binomiali (n choose k) senza overflow è utilizzare il triangolo di Pascal. Non sono necessarie frazioni o moltiplicazioni. (n choose k). La riga nth e la voce kth del triangolo di Pascal forniscono il valore.

Take a look at this page. Si tratta di un'operazione O(n^2) con solo aggiunta, che è possibile risolvere con la programmazione dinamica. Sarà veloce come un fulmine per qualsiasi numero che possa rientrare in un numero intero a 64 bit.

Answer 6

Se avete intenzione di calcolare molte combinazioni come questo, calcolando Triangolo del Pascal è che l'opzione migliore. Come già sapete la formula ricorsiva, penso di poter passato un certo codice qui:

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

Ecco la mia versione, che funziona esclusivamente in numeri interi (la divisione per k produce sempre un quoziente intero) ed è veloce a O (k):

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

ho scritto in modo ricorsivo perché è così semplice e carina, ma si potrebbe trasformare in una soluzione iterativa, se volete.

Answer 8

Il modo più veloce è probabilmente utilizzare la formula, e non il triangolo di pascal. Iniziamo a non fare moltiplicazioni quando sappiamo che stiamo andando a dividere per lo stesso numero più tardi. Se k < n/2, abbiamo k = n - k.Sappiamo che C (n, k) = C (n, n-k) Ora:

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

Almeno con questa tecnica, non si è mai dividere per un numero che è stato utilizzato per moltiplicare prima. Hai le moltiplicazioni (n-k) e le divisioni (n-k).

Sto pensando a un modo per evitare tutte le divisioni, trovando GCD tra i numeri che dobbiamo moltiplicare e quelli che dobbiamo dividere. Proverò a modificare più tardi.