Compter efficacement les combinaisons et les permutations

deux suggestions assez simples:

1. pour éviter les débordements, faites tout dans l'espace de log. Utiliser le fait que log(a * b) = log(a) + log(b) et log(a / b) = log(a) - log(b). Cela rend facile de travailler avec de très grands factoriels: log (n! / m!) = log(n!)- log(m!), etc.

2. utilisez la fonction gamma au lieu de factorielle. Vous pouvez en trouver un dans scipy.stats.loggamma . C'est une façon beaucoup plus efficace de calculer les facteurs logarithmiques plutôt que la sommation directe. loggamma(n) == log(factorial(n - 1)) , et de même, gamma(n) == factorial(n - 1) .

si vous n'avez pas besoin d'une solution de python pur, gmpy2 pourrait vous aider ( gmpy2.comb est très rapide).

il y a une fonction pour ceci en scipy qui n'a pas encore été mentionnée: scipy.spécial.peigne . Il semble efficace basé sur quelques résultats de chronométrage rapide pour votre doctest (~0.004 secondes pour comb(100000, 1000, 1) == comb(100000, 99000, 1) ).

[alors que cette question spécifique semble être au sujet des algorithmes la question est-il une fonction ncr de mathématiques en python est marquée comme un duplicata de ceci...]

si votre problème ne nécessite pas de connaître le nombre exact de permutations ou de combinaisons, alors vous pouvez utiliser approximation de Stirling pour le factoriel.

qui conduirait à un code comme celui-ci:

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

si vous calculez N choose K (ce que je pense que vous faites avec ncr), il y a une solution de programmation dynamique qui peut être beaucoup plus rapide. Cela évitera les factoriels, en plus vous pouvez garder la table si vous voulez pour une utilisation ultérieure.

voici un lien d'enseignement pour cela:

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

Je ne sais pas comment mieux résoudre votre premier problème, si, désolé.

Edit: Voici la maquette. Il y a quelques assez hilarant tout-en-un d'erreurs, de sorte qu'il peut certainement être plus propre.

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]

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

devrait vous permettre de compter les combinaisons

solution plus efficace pour nCr - espace sage et précision Sage.

l'intermédiaire (res) est garanti d'être toujours int et jamais plus grand que le résultat. La complexité de l'espace est O(1) (Pas de liste, pas de fermeture éclair, pas de pile), la complexité du temps est O (r) - exactement R multiplications et R divisions.

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

en utilisant xrange() au lieu de range() accélérera légèrement les choses en raison du fait qu'aucune liste intermédiaire n'est créée, peuplée, itérée et ensuite détruite. Aussi, reduce() avec operator.mul .

pour n choisir K vous pourriez utiliser le triangle Pascals. Fondamentalement, vous auriez besoin de garder le tableau de la taille N autour pour calculer toutes les valeurs de n choisir K. Seulement des ajouts seraient nécessaires.

vous pouvez entrer deux entiers et importer bibliothèque de mathématiques pour trouver le factoriel, puis appliquer la formule nCr

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