подсчет комбинаций и перестановок эффективно
У меня есть некоторый код для подсчета перестановок и комбинаций, и я пытаюсь заставить его работать лучше на большие количества.
Я нашел лучший алгоритм для перестановок, который избегает больших промежуточных результатов, но я все еще думаю, что могу добиться большего успеха для комбинаций.
До сих пор я вставил особый случай для отражения симметрии NCR, но я все еще хотел бы найти лучший алгоритм, который избегает вызова к факториалу (r), который является излишне большим промежуточным результатом. Без этой оптимизации последний doctest берет слишком долго попытку вычислить факториал (99000).
Кто-либо может предложить более эффективный способ считать комбинации?
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)
7 ответов
Если n не далеко от R, то использование рекурсивного определения комбинации, вероятно, лучше, поскольку Xc0 = = 1 У вас будет несколько итераций:
только соответствующее рекурсивное определение здесь:
NCR = (N-1) C (R - 1) * N / R
Это может быть красиво вычислено с помощью хвоста Рекурсия со следующим списком:
[(N - R, 0), (N - R + 1, 1), (N - R + 2, 2), ..., (N - 1, R - 1), (N, R )]
, который, конечно, легко генерируется в Python (мы опускаем первую запись с NC0 = 1) на Теперь нам просто нужно применять шаг рекурсии, используя рекурсию хвоста с уменьшением. Начнем с 1, поскольку NC0 равно 1, а затем умножьте текущее значение с помощью следующей записи из списка, как показано ниже. IZIP (XRANGE (N - R + 1, N + 1), Xrange (1, R + 1 )) Обратите внимание, что это предполагает R <= n, вам нужно проверить это и поменять их, если они нет. Также оптимизировать использование, если R 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)
Для n Выберите K Вы можете использовать треугольник Pascals. По сути, вам нужно будет поддерживать массив размера N, чтобы вычислить все значения n выбора k. Требуются только дополнения.
Использование XRANGE () вместо диапазона () будет незначительно ускорить вещи из-за того, что промежуточный список не создан, заполняется, а затем, а затем разрушен. Кроме того, уменьшается () с помощью оператора. Суль .
Две довольно простые предложения:
, чтобы избежать переполнения, сделайте все в пространстве журнала. Используйте тот факт, что журнал (A * B) = log (a) + log (b) и log (a / b) = log (a) - log (b). Это позволяет легко работать с очень большими факториалами: log (n! / M!) = Log (n!) - log (m!) И т. Д.
Используйте функцию гамма вместо факториала. Вы можете найти один в
Scipy.Stats.loggamma. Это гораздо более эффективный способ рассчитать факториалы журнала, чем прямое суммирование.loggamma (n) == Журнал (факториал (n - 1)), а также аналогичногамма (N) == факториал (N - 1).
Если ваша проблема не требует знания точного количества перестановок или комбинаций, вы можете использовать приближение Стирлинга для факториала.
Это приведет к тому, что это приведет к следующему коду:
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
Если вам не нужен решение Pure-Python, GMPY2 может помочь ( gmpy2.comb очень быстро).
Если вы вычисляете выберите K (что я думаю, что вы делаете с NCR), существует динамическое программирование, которое может быть намного быстрее. Это позволит избежать факториала, плюс вы можете сохранить таблицу, если хотите для более позднего использования.
Вот преподавательская ссылка для него:
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/dyprog.html
Я не уверен, как лучше решить Первая проблема, хотя, извините.
Редактировать: вот макет. Есть несколько довольно веселых ошибок, поэтому он, безусловно, может стоять немного более чистой.
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]