大規模な組み合わせに対するこのアルゴリズムを最もコンパクトな方法で記述するにはどうすればよいでしょうか?

StackOverflow https://stackoverflow.com/questions/956542

質問

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

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

例としては、次の組み合わせが何通りあるかが挙げられます。 6 Balls のドラムから引き出すことができます 48 Balls 宝くじの抽選で。

この式を最適化して、最小の時間計算量 O で実行します。

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

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

何人かの人が解決策に取り組んだ後、そのディスカッションから得た情報やリンクをいくつか投稿します。

どの言語でも受け入れられます。

役に立ちましたか？

解決

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

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

倍精度と反復二乗を使用して累乗を実行する場合、演算は次のようになります。

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

少し賢くすれば操作の数を減らすことができるかもしれませんが、このアプローチでは合計時間の複雑さは O(log n) になります。かなり扱いやすい。

編集：この計算がどれほど一般的であるかを考えると、このトピックに関する学術文献も数多く存在するはずです。優れた大学図書館は、それを追跡するのに役立つ可能性があります。

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

他のヒント

パイソン: ○(分[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-i そして 1+i 一定のサイズを持つと考えることができます。
  • 各乗算のコストも直線的に増加します。
  • すべての反復のこの合計は、次の等差級数になります。 k.

私の結論： ○(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

私はそれを解決したいのMathematicaするます：

Binomial[n, k]

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

パイソン: での近似 ○(1) ?

Python 10 進数実装を使用して近似値を計算します。外部ループを使用しておらず、数に制限があるため、 で実行されると思います。 ○(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までに制限されているようです。

NおよびKの値の合理的な数を考慮すると、事前にそれらを計算し、ルックアップテーブルを使用します。

これは、いくつかのファッション（あなたは、計算負荷を軽減している）に問題を逃れだが、それはあなたが値の大きな数を決定するために持っている場合に有用な技術です。

MATLAB:

  • 詐欺師のやり方（組み込み関数を使用） ンチョセク): 13文字、O(?)

    nchoosek(N,k)

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

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)

私は、これは本当に古い質問です知っているが、私は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;
}

最終的なコードは、あなたがそれを実行するまで、それがうまくいくと信じていませんので簡単です。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top