эффективный подсчет комбинаций и перестановок

Question

У меня есть некоторый код для подсчета перестановок и комбинаций, и я пытаюсь заставить его работать лучше для больших чисел.

Я нашел лучший алгоритм для перестановок, который позволяет избежать больших промежуточных результатов, но явсе еще думаю, что я могу сделать лучше для комбинаций.

Пока что я поместил в специальный случай, чтобы отразить симметрию nCr, но я все же хотел бы найти лучший алгоритм, который избегает вызова факториала(г), который является излишне большим промежуточным результатом.Без этой оптимизации последний док-тест занимает слишком много времени, пытаясь вычислить факториал (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)

Answer 1

если 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) с помощью izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Обратите внимание, что это предполагает, что r <= n, вам нужно проверить это и поменять их местами, если это не так. Также для оптимизации использования, если r <n / 2, то r = n - r. </p>

Теперь нам просто нужно применить шаг рекурсии, используя хвостовую рекурсию с помощью Reduce. Мы начинаем с 1, поскольку nC0 равно 1, а затем умножаем текущее значение на следующую запись из списка, как показано ниже.

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

Два довольно простых предложения:

1. Чтобы избежать переполнения, делайте все в пространстве журнала. Используйте тот факт, что log (a * b) = log (a) + log (b), а log (a / b) = log (a) - log (b). Это облегчает работу с очень большими факториалами: log (n! / M!) = Log (n!) - log (m!) И т. Д.

2. Используйте гамма-функцию вместо факториала. Вы можете найти его в scipy.stats.loggamma. Это гораздо более эффективный способ вычисления логарифмических коэффициентов, чем прямое суммирование. loggamma(n) == log(factorial(n - 1)) и аналогично gamma(n) == factorial(n - 1).

Answer 3

В scipy есть функция для этого, которая еще не упоминалась: scipy.special.comb . Это кажется эффективным, основываясь на некоторых быстрых временных результатах для вашего doctest (~ 0,004 секунды для comb(100000, 1000, 1) == comb(100000, 99000, 1)).

[Хотя этот конкретный вопрос, похоже, касается алгоритмов, вопрос есть ли в python математическая функция ncr помечена как дубликат этого ...]

Answer 4

Если вам не нужно решение на чистом python, gmpy2 может помочь (gmpy2.comb очень быстро).

Answer 5

Если ваша задача не требует знания точного числа перестановок или комбинаций, то вы можете использовать приближение Стирлинга для факториала.

Это привело бы к такому коду:

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 6

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

должно позволять вам считать комбинации

Answer 7

Если вы вычисляете N, выберите 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]

Answer 8

from numpy import prod

def nCr(n,r):
    numerator = range(n, max(n-r,r),-1)
    denominator = range(1, min(n-r,r) +1,1)
    return int(prod(numerator)/prod(denominator))

Answer 9

Более эффективное решение для nCr - в пространстве и точности.

Посредник (res) гарантированно всегда будет int и никогда не будет больше результата. Пространственная сложность O (1) (без списков, без почтовых индексов, без стека), временная сложность O (r) - ровно r умножений и 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

Answer 10

Вы можете ввести два целых числа и импортировать математическую библиотеку, чтобы найти факториал, а затем применить формулу nCr

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