Come si può scrivere questo algoritmo per le grandi combinazioni nel modo più compatto?

Question

Il numero di combinazioni di elementi k che possono essere recuperati da elementi N è descritto dalla seguente formula.

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

Un esempio potrebbe essere il numero di combinazioni di 6 Balls si può trarre da un tamburo di 48 Balls in una lotteria.

Ottimizza questa formula per correre con la più piccola complessità temporale O

Questa domanda è stata ispirata dal nuovo motore matematica WolframAlpha e il fatto che è in grado di calcolare estremamente grandi combinazioni molto rapidamente. per esempio. e una successiva discussione sul tema su un altro forum.

  

http://www97.wolframalpha.com/input/?i = 20000000 + scegliere + 15000000

Vi posto alcune informazioni / link da quella discussione, dopo alcune persone prendere una pugnalata alla soluzione.

Ogni lingua è accettabile.

Answer 1

Si noti che WolframAlpha restituisce un "Decimale approssimazione". Se non avete bisogno di una precisione assoluta, si potrebbe fare la stessa cosa per il calcolo dei fattoriali con approssimazione di Stirling .

Ora, approssimazione di Stirling richiede la valutazione di (n / e) ^ n, dove e è la base del logaritmo naturale, che sarà di gran lunga l'operazione più lenta. Ma questo può essere fatto utilizzando le tecniche descritte nel un altro post StackOverflow .

Se si utilizza la doppia precisione e ripetuti quadratura per compiere l'elevamento a potenza, le operazioni saranno:

• 3 valutazioni di approssimazione Stirling, ciascuna O richiede (log n) moltiplicazioni e una valutazione radice quadrata.
• 2 moltiplicazioni
• 1 divisioni

Il numero di operazioni potrebbe probabilmente essere ridotto con un po 'di intelligenza, ma la complessità totale tempo sta per essere O (log n) con questo approccio. Abbastanza gestibile.

EDIT: C'è destinato anche ad essere un sacco di letteratura accademica su questo argomento, dato quanto sia comune questo calcolo è. Una buona biblioteca universitaria potrebbe aiutare a seguirlo verso il basso.

EDIT2: Inoltre, come sottolineato in un'altra risposta, i valori saranno facilmente traboccare una, quindi un tipo doppio punto mobile con precisione molto estesa dovrà essere utilizzato per moderatamente grandi valori anche di k e n

.

Answer 2

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

Analisi:

• Le dimensioni p e q aumenta linearmente all'interno del ciclo, se n-i e 1+i possono essere considerate come aventi dimensione costante.
• Il costo di ogni moltiplicazione sarà quindi anche aumentare linearmente.
• Questa somma di tutte le iterazioni diventa una serie aritmetica k.

La mia conclusione: O (k ² )

Se riscritto per utilizzare numeri in virgola mobile, le moltiplicazioni saranno operazioni atomiche, ma perderanno un sacco di precisione. E 'trabocca anche per choose(20000000, 15000000). (Non è una grande sorpresa, dal momento che il risultato sarebbe intorno ,2119,620413 millions × 10 ^4.884.378 ).

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

Answer 3

Mi piacerebbe risolvere in Mathematica :

Binomial[n, k]

L'uomo, che è stato facile ...

Answer 4

Python:? approssimazione in O (1)

Utilizzando implementazione di Python decimali per calcolare un'approssimazione. Dal momento che non fa uso di alcun circuito esterno, ed i numeri sono limitati in termini di dimensioni, penso che verrà eseguito in 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)

Esempio:

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

più in alto, e traboccherà. L'esponente sembra essere limitato a 40 milioni.

Answer 5

Dato un numero ragionevole di valori per n e K, li calcolare in anticipo e utilizzare una tabella di ricerca.

E 'schivare la questione in qualche modo (si sta scaricando il calcolo), ma è una tecnica utile se si hanno per determinare un gran numero di valori.

Answer 6

MATLAB:

• La maniera del baro (usando la funzione built-in NCHOOSEK ): 13 caratteri, o ()

  nchoosek(N,k)
  

• La mia soluzione: 36 caratteri, O (min (k, N-k))

  a=min(k,N-k);
  prod(N-a+1:N)/prod(1:a)
  

Answer 7

So che questa è una domanda veramente vecchio, ma ho lottato con una soluzione a questo problema per lungo tempo fino a quando ho trovato davvero un semplice scritto in VB 6 e dopo il porting in C #, ecco il risultato:

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

Il codice finale è così semplice da non credere che funzionerà fino a quando lo si esegue.

Inoltre, il originale articolo dà qualche bella spiegazione di come ha raggiunto l'algoritmo finale .