37

順列と組み合わせをカウントするコードがいくつかあり、多数の場合にうまく機能するようにしようとしています。

大規模な中間結果を回避する順列のより良いアルゴリズムを見つけましたが、組み合わせについてはまだ改善できると思います。

これまでのところ、nCr の対称性を反映するために特別なケースを用意しましたが、不必要に大きな中間結果である factorial(r) の呼び出しを回避するより良いアルゴリズムを見つけたいと思っています。この最適化を行わないと、最後の doctest で factorial(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)
4

13 に答える 13

27

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です。

ここで、reduceを使用した末尾再帰を使用して再帰ステップを適用する必要があります。nC0は1であるため、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-19T20:11:44.287 に答える
20

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)。

于 2010-01-19T20:40:55.333 に答える
8

純粋なPythonソリューションが必要ない場合は、gmpy2が役立つ可能性があります（gmpy2.comb非常に高速です）。

于 2010-01-19T22:30:08.093 に答える
5

N choose 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]
于 2010-01-19T20:16:24.310 に答える
4

問題が順列または組み合わせの正確な数を知る必要がない場合は、階乗にスターリングの近似を使用できます。

それは次のようなコードにつながります：

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-19T20:58:39.000 に答える
0

N には K を選択すると、パスカルの三角形を使用できます。基本的に、すべての N 選択 K 値を計算するには、サイズ N の配列を維持する必要があります。追加のみが必要です。

于 2010-01-19T20:47:58.260 に答える
0

xrange()代わりにを使用するrange()と、中間リストの作成、入力、反復、および破棄が行われないため、処理がわずかに高速化されます。また、reduce()とoperator.mul。

于 2010-01-19T20:14:32.033 に答える