40

n choose k の値を評価する最も効率的な方法は何ですか? 私が考える力ずくの方法は、 n factorial / k factorial / (nk) factorial を見つけることです。

より良い戦略は、この再帰的な式に従って dp を使用することです。n choose k を評価するための他のより良い方法はありますか?

4

8 に答える 8

48

これは私のバージョンで、純粋に整数で動作し (k による除算は常に整数の商を生成します)、O(k) で高速です。

function choose(n, k)
    if k == 0 return 1
    return (n * choose(n - 1, k - 1)) / k

とてもシンプルできれいなので、再帰的に書きましたが、必要に応じて反復ソリューションに変換できます。

于 2013-03-08T20:10:08.527 に答える
38

これには乗法式を使用できます。

ここに画像の説明を入力

http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

于 2013-03-08T20:06:44.713 に答える
7

おそらく、(n choose k)オーバーフローせずに二項係数を計算する最も簡単な方法は、パスカルの三角形を使用することです。分数や掛け算は必要ありません。(n choose k). パスカルの三角形の行とエントリが値を示しますnth。kth

このページを見てください。これはO(n^2)足し算だけの演算で、動的計画法で解くことができます。64 ビット整数に収まる任意の数値に対して、超高速になります。

于 2013-03-08T20:02:36.933 に答える
5

このように多くの組み合わせを計算する場合は、パスカルの三角形を計算するのが最適なオプションです。再帰式はすでにご存知のとおり、ここにいくつかのコードを貼り付けることができると思います。

MAX_N = 100
MAX_K = 100

C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]

for i in range(1, MAX_N+1):
    for j in range(1, MAX_K+1):
        C[i][j] = C[i-1][j-1] + C[i-1][j];

print C[10][2]
print C[10][8]
print C[10][3]
于 2013-03-08T20:08:10.067 に答える
1

このアプローチの問題はn!/k!(n-k)!、コストと!いうよりも、非常に急速に成長するという問題です。そのため、値がnCk64 ビット整数の範囲内にある場合でも、中間計算はそうで​​はありません。kainaw の再帰的加算アプローチが気に入らない場合は、乗算的アプローチを試すことができます。

nCk == product(i=1..k) (n-(k-i))/i

whereは、 whenが値を取るproduct(i=1..k)すべての項の積を意味します。i1,2,...,k

于 2013-03-08T19:54:59.797 に答える
1

最速の方法は、おそらくパスカルの三角形ではなく、式を使用することです。後で同じ数で割ることになることがわかっているときは、掛け算をしないようにしましょう。k < n/2 の場合、k = n - k とします。C(n,k) = C(n,nk) であることがわかっています。

n! / (k! x (n-k)!) = (product of numbers between (k+1) and n) / (n-k)!

少なくともこの手法を使用すると、以前は乗算していた数値で除算することはありません。(nk) 個の乗算と (nk) 個の除算があります。

乗算する必要のある数値と除算する必要のある数値の間の GCD を見つけることによって、すべての除算を回避する方法を考えています。後で編集してみます。

于 2013-03-08T20:20:23.520 に答える
0

階乗のルックアップ テーブルがある場合、C(n,k) の計算は非常に高速になります。

于 2013-03-08T19:53:09.440 に答える
-4

"Most efficient" is a poor request. What are you trying to make efficient? The stack? Memory? Speed? Overall, my opinion is that the recursive method is most efficient because it only uses addition (a cheap operation) and the recursion won't be too bad for most cases. The function is:

nchoosek(n, k)
{
    if(k==0) return 1;
    if(n==0) return 0;
    return nchoosek(n-1, k-1)+nchoosek(n-1,k);
}
于 2013-03-08T19:45:52.260 に答える