有效地計數組合和排列

我有一些代碼來計算排列和組合，我試圖讓它對大數量更好。有效地計數組合和排列

我發現一種避免大的中間結果的排列更好的算法，但我仍然認爲我可以做的更好的組合。到目前爲止，我已經放入了一個特例來反映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)

來源

2010-01-19 Christian Oudard

如果n不遠處，則成爲使用組合的遞歸定義可能是更好的，因爲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。

現在我們只需要應用使用tail遞歸和遞歸的遞歸步驟。我們從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)

來源

2010-01-19 20:11:44 wich

對於單個nCr的，這是更好的，但是當你有多個NCR公司（N的順序），那麼動態規劃方法比較好，即使它有很長的準備時間，因爲它不會溢出除非必要，否則變成'bignum'。 – JPvdMerwe 2010-01-20 06:39:54

使用的xrange()代替range()將略微加快速度，由於沒有中間列表中創建，填充，通過迭代，然後摧毀了這一事實。另外，reduce()與operator.mul。

來源

2010-01-19 20:14:32

對不起，我的代碼是python 3，而不是python 2. python 3中的範圍與python 2中的xrange相同。 – 2010-01-19 20:16:03

如果您是計算ñ選擇K（這是我認爲你與NCR做的），有一個動態編程解決方案，可能會快很多。這將避免factorial，如果您想以後使用，您可以保留表格。

這裏是一個教學環節吧：

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]

來源

2010-01-19 20:16:24 agorenst

似乎這個實現是O（n^2），而我放置的尾遞歸據我所知，O（n）是O（n）。 – wich 2010-01-19 20:23:23

它似乎使用了不同的遞歸定義。這裏n選擇k = n-1選擇k-1 + n-1選擇k，而我用n選擇k = n-1選擇k-1 * n/k – wich 2010-01-19 20:30:29

事實上，情況就是如此。我將很快編輯這篇文章，包括一個快速的python模型的算法。你的速度要快得多。我會在這裏留下我的帖子，以防萬一Gorgapor擁有一些需要數小時才能完成乘法的異域機器。 >> – agorenst 2010-01-19 21:40:41

兩個相當簡單的建議：

爲了避免溢出，做日誌空間的一切。使用log（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) == log(factorial(n - 1))，同樣地，gamma(n) == factorial(n - 1)。

來源

2010-01-19 20:40:55 dsimcha

好的建議，在日誌空間做事情。不清楚「精確度」是什麼意思。不會使用log-floats導致大數字的舍入錯誤？ – 2010-01-20 14:38:29

@Gorgapor：我想一個更清楚的說法是：「避免溢出」。編輯。 – dsimcha 2010-01-20 15:27:37

請注意，由於浮點數字的精度有限，這不會給出準確的結果。 – starblue 2010-01-20 19:58:58

對於N選擇K，可以使用Pascals三角形。基本上你需要保持大小爲N的數組來計算所有N個選擇K值。只需要添加。

來源

2010-01-19 20:47:58 Richie

這基本上是Agor建議的，但它會是O（n^2）。由於現在使用乘法和除法並不是問題，所以使用不同的遞歸關係可以使算法O（n）如我所述。 – wich 2010-01-19 20:53:14

如果您的問題不需要知道排列或組合的確切數量，那麼您可以使用Stirling's approximation作爲階乘。

這將導致這樣的代碼：

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

來源

2010-01-19 20:58:39 unutbu

階乘的主要問題是結果的大小，而不是計算它的時間。此外，這裏的結果值比浮點值可以準確表示的要大得多。 – 2010-01-20 14:34:36

如果你並不需要一個純Python的解決方案，gmpy2可能幫助（gmpy2.comb是非常快的）。

來源

2010-01-19 22:30:08

感謝您的參考，這是一個非常好的實用解決方案。這對我來說更像是一個學習項目，所以我對算法比實際結果更感興趣。 – 2010-01-20 14:35:29

對於那些寫了幾年後纔回答這個問題的人，gmpy現在被稱爲gmpy2。 – 2015-01-03 17:41:05

你可以輸入兩個整數和進口數學庫中查找階乘，然後應用NCR的公式

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

來源

2013-04-01 05:27:48

還有哪些尚未提到這SciPy的功能：scipy.special.comb。基於文檔測試的一些快速計時結果，這似乎很有效（comb(100000, 1000, 1) == comb(100000, 99000, 1)〜0.004秒）。

[雖然這個具體的問題似乎是關於算法的問題is there a math ncr function in python被標記爲這個副本...]

來源

2013-08-26 11:39:34 dshepherd

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

應該讓你數組合

來源

2017-02-06 04:41:31 Divyansh

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

來源

2017-06-17 02:35:22 ZXX

有效地計數組合和排列

回答

相關問題