contando efficacemente combinazioni e permutazioni

Question

Ho un codice per contare permutazioni e combinazioni e sto cercando di farlo funzionare meglio per grandi numeri.

Ho trovato un algoritmo migliore per permutazioni che evita grandi risultati intermedi, ma penso ancora che possa fare meglio per le combinazioni.

Finora, ho inserito un caso speciale per riflettere la simmetria di nCr, ma mi piacerebbe comunque trovare un algoritmo migliore che eviti la chiamata a factorial (r), che è un risultato intermedio inutilmente grande . Senza questa ottimizzazione, l'ultimo doctest impiega troppo tempo nel calcolare fattoriale (99000).

Qualcuno può suggerire un modo più efficiente per contare le combinazioni?

from math import factorial 

def product(iterable): 
    prod = 1 
    for n in iterable: 
     prod *= n 
    return prod 

def npr(n, r): 
    """ 
    Calculate the number of ordered permutations of r items taken from a 
    population of size n. 

    >>> npr(3, 2) 
    6 
    >>> npr(100, 20) 
    1303995018204712451095685346159820800000 
    """ 
    assert 0 <= r <= n 
    return product(range(n - r + 1, n + 1)) 

def ncr(n, r): 
    """ 
    Calculate the number of unordered combinations of r items taken from a 
    population of size n. 

    >>> ncr(3, 2) 
    3 
    >>> ncr(100, 20) 
    535983370403809682970 
    >>> ncr(100000, 1000) == ncr(100000, 99000) 
    True 
    """ 
    assert 0 <= r <= n 
    if r > n // 2: 
     r = n - r 
    return npr(n, r) // factorial(r) 

Answer 1

se n non è lontano da r quindi utilizzando la definizione ricorsiva di combinazione è probabilmente meglio, dal momento che xC0 == 1 si avrà solo poche iterazioni:

La definizione ricorsiva rilevante è:

nCr = (n-1) C (R-1) * n/r

Questo può essere ben calcolata utilizzando la ricorsione in coda con il seguente elenco:

[(n - r, 0), (n - r + 1, 1), (n - r + 2, 2), ..., (n - 1, r - 1), (n, r)]

che è ovviamente facilmente generato in Python (omettiamo la prima voce da nC0 = 1) per izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Si noti che ciò presuppone r < = n è necessario verificarlo e scambiarli se non lo sono. Anche per ottimizzare l'uso se r < n/2 quindi r = n - r.

Ora abbiamo semplicemente bisogno di applicare la fase di ricorsione utilizzando la ricorsione della coda con riduzione. Iniziamo con 1 poiché nC0 è 1 e quindi moltiplichiamo il valore corrente con la voce successiva dall'elenco come di seguito.

from itertools import izip 

reduce(lambda x, y: x * y[0]/y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1) 

Answer 2

Utilizzando xrange() anziché range() accelererà cose leggermente a causa del fatto che non si generino lista intermedia, popolato, iterata attraverso, e poi distrutta. Inoltre, reduce() con operator.mul.

Answer 3

Se stai calcolando N scegli K (che è quello che penso che stai facendo con ncr), c'è una soluzione di programmazione dinamica che potrebbe essere molto più veloce. Questo eviterà fattoriale, in più puoi tenere il tavolo se lo desideri per un uso successivo.

Ecco un link di insegnamento per esso:

http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html

non sono sicuro di come risolvere al meglio il tuo primo problema, però, mi dispiace.

Modifica: ecco il mock-up. Ci sono alcuni errori off-by-one piuttosto esilaranti, quindi può certamente stare un po 'più pulito.

import sys 
n = int(sys.argv[1])+2#100 
k = int(sys.argv[2])+1#20 
table = [[0]*(n+2)]*(n+2) 

for i in range(1,n): 
    table[i][i] = 1 
for i in range(1,n): 
    for j in range(1,n-i): 
     x = i+j 
     if j == 1: table[x][j] = 1 
     else: table[x][j] = table[x-1][j-1] + table[x-1][j] 

print table[n][k] 

Answer 4

Due suggerimenti abbastanza semplici:

1. per evitare l'overflow, fare tutto nello spazio di log.Usa il log (a * b) = log (a) + log (b) e log (a/b) = log (a) - log (b). In questo modo è facile lavorare con grandi fattoriali: log = log (n!) - log (m!), Ecc

2. Utilizzare la funzione gamma, invece di fattoriale (n/m!!). Puoi trovarne uno in scipy.stats.loggamma. È un modo molto più efficiente per calcolare i log-factorials rispetto alla sommatoria diretta. loggamma(n) == log(factorial(n - 1)) e, analogamente, gamma(n) == factorial(n - 1).

Answer 5

Per N scegliere K è possibile utilizzare il triangolo di Pascal. Fondamentalmente avresti bisogno di mantenere un array di dimensioni N intorno per calcolare tutti i valori N di scegliere K. Sarebbero necessarie solo aggiunte.

Answer 6

Se il problema non richiede la conoscenza del numero esatto di permutazioni o combinazioni, è possibile utilizzare Stirling's approximation per il fattoriale.

che avrebbe portato alla codice come questo:

import math 

def stirling(n): 
    # http://en.wikipedia.org/wiki/Stirling%27s_approximation 
    return math.sqrt(2*math.pi*n)*(n/math.e)**n 

def npr(n,r): 
    return (stirling(n)/stirling(n-r) if n>20 else 
      math.factorial(n)/math.factorial(n-r)) 

def ncr(n,r):  
    return (stirling(n)/stirling(r)/stirling(n-r) if n>20 else 
      math.factorial(n)/math.factorial(r)/math.factorial(n-r)) 

print(npr(3,2)) 
# 6 
print(npr(100,20)) 
# 1.30426670868e+39 
print(ncr(3,2)) 
# 3 
print(ncr(100,20)) 
# 5.38333246453e+20 

Answer 7

Se non avete bisogno di una soluzione di pura-python, gmpy2 potrebbe aiutare (gmpy2.comb è molto veloce).

Answer 8

è possibile introdurre due numeri interi e libreria di importazione matematica per trovare il fattoriale e quindi applicare la formula nCr

import math 
n,r=[int(_)for _ in raw_input().split()] 
f=math.factorial 
print f(n)/f(r)/f(n-r) 

Answer 9

C'è una funzione per questo in SciPy che non è stato ancora citato: scipy.special.comb. Sembra efficiente sulla base di alcuni risultati rapidi per il tuo doctest (~ 0.004 secondi per comb(100000, 1000, 1) == comb(100000, 99000, 1)).

[Anche se questa specifica questione sembra essere di algoritmi la questione is there a math ncr function in python è contrassegnato come un duplicato di questo ...]

Answer 10

from scipy import misc 
misc.comb(n, k) 

dovrebbe consentire di contare le combinazioni

Answer 11

soluzione più efficiente a favore nCr - spazio saggio e precisione saggio.

L'intermediario (res) è garantito per essere sempre int e mai più grande del risultato. La complessità dello spazio è O (1) (nessuna lista, nessuna cerniera, nessuna pila), la complessità temporale è O (r) - esattamente r moltiplicazioni e divisioni r.

def ncr(n, r): 
    r = min(r, n-r) 
    if r == 0: return 1 
    res = 1 
    for k in range(1,r+1): 
     res = res*(n-k+1)/k 
    return res