2

kアイテムから取得できるアイテムの組み合わせの数はN、次の式で表されます。

             N! 
c =  ___________________ 
       (k! * (N - k)!)

例としては、宝くじで6 Ballsのドラム缶から の組み合わせをいくつ引き出すことができるかが挙げられます。48 Balls

この数式を最適化して、最小の O 時間の複雑さで実行します

この質問は、新しい WolframAlpha 数学エンジンと、非常に大きな組み合わせを非常に高速に計算できるという事実に触発されました。たとえば、別のフォーラムでのトピックに関するその後の議論。

http://www97.wolframalpha.com/input/?i=20000000+Choose+15000000

一部の人々が解決策を試した後、その議論からいくつかの情報/リンクを投稿します。

どの言語でも構いません。

4

7 に答える 7

6

Python: O (min[ k , n - k ] 2 )

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

分析：

  • と が一定のサイズであると見なすことができる場合、pとのサイズはqループ内で直線的に増加します。n-i1+i
  • 各乗算のコストも直線的に増加します。
  • このすべての反復の合計は、 の算術級数になりkます。

私の結論: O ( k2 )

浮動小数点数を使用するように書き直すと、乗算はアトミック操作になりますが、多くの精度が失われます。のオーバーフローさえありchoose(20000000, 15000000)ます。(結果は約 0.2119620413×10 4884378になるので、大きな驚きではありません。)

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result
于 2009-06-05T15:46:30.397 に答える
5

WolframAlpha は「10 進近似」を返すことに注意してください。絶対的な精度が必要ない場合は、スターリングの近似を使用して階乗を計算することで同じことを行うことができます。

ここで、スターリングの近似には (n/e)^n の評価が必要です。ここで、e は自然対数の底であり、これは最も遅い演算になります。しかし、これは、別のスタックオーバーフローの投稿で概説されている手法を使用して実行できます。

累乗を行うために倍精度と繰り返し二乗を使用する場合、演算は次のようになります。

  • スターリング近似の 3 つの評価。それぞれに O(log n) の乗算と 1 つの平方根の評価が必要です。
  • 2回の掛け算
  • 1区画

操作の数はおそらく少し巧妙に減らすことができますが、このアプローチでは合計時間の複雑さは O(log n) になります。かなり扱いやすい。

編集: この計算がいかに一般的であるかを考えると、このトピックに関する多くの学術文献もあるはずです。優れた大学図書館は、それを追跡するのに役立ちます。

EDIT2: また、別の応答で指摘されているように、値は double を簡単にオーバーフローするため、k と n の値が適度に大きい場合でも、精度が非常に拡張された浮動小数点型を使用する必要があります。

于 2009-06-05T16:12:44.523 に答える
2

私はMathematicaでそれを解決します：

Binomial[n, k]

男、それは簡単だった...

于 2009-06-05T15:45:15.780 に答える
2

Python: O (1)での近似?

Python decimal 実装を使用して近似値を計算します。外部ループを使用しておらず、数も限られているので、 O (1)で実行できると思います。

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

例：

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

それ以上になると、オーバーフローします。指数は40000000に制限されているようです。

于 2009-06-09T22:59:50.537 に答える
1

これは非常に古い質問であることは知っていますが、VB 6 で書かれた非常に単純な問題を見つけて C# に移植した後、この問題の解決策に長い間苦労しました。結果は次のとおりです。

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

最終的なコードは非常に単純なので、実行するまで機能するとは思えません。

また、元の記事では、彼がどのようにして最終的なアルゴリズムに到達したかについて、いくつかの素晴らしい説明を提供しています。

于 2012-03-20T18:58:32.747 に答える
1

n と K の妥当な数の値を指定して、それらを事前に計算し、ルックアップ テーブルを使用します。

何らかの方法で問題を回避していますが (計算をオフロードしています)、多数の値を決定する必要がある場合に便利な手法です。

于 2009-06-05T15:53:30.803 に答える
1

MATLAB:

  • 詐欺師のやり方 (組み込み関数NCHOOSEKを使用): 13 文字、O(?)

    nchoosek(N,k)

  • 私の解決策: 36 文字、O(min(k,Nk))

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)
于 2009-06-05T16:22:15.650 に答える