問題タブ [binomial-coefficients]

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

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

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

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

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

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

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

...できればJavaで。ここに私が持っているものがあります:

これを行うより良い方法があるかどうか疑問に思っていますか？

10000のオーダーの「n」個の計算を可能にするPythonで二項検定を実行する必要があります。

scipy.misc.combを使用して簡単なbinomial_test関数を実装しましたが、階乗または組み合わせ自体を計算しているときに表現可能な最大数に達するため、n=1000付近にかなり制限されていると思います。これが私の関数です：

その二項確率を計算するために、ネイティブのpython（またはnumpy、scipy ...）関数をどのように使用できますか？可能であれば、scipy0.7.2互換のコードが必要です。

どうもありがとう！

二項係数の配列を維持するためにダブルチェック ロックを使用しようとしていますが、ダブルチェック ロックが機能しないことを最近読みました。効率は非常に重要であるため、条件ステートメント内でのみ使用しない限り、volatile を使用することはできません。シングルトンオブジェクトで静的クラスを使用する方法がわかりません（これはフレームワークの一部であり、関数を使用する必要がある数値の種類がわからないため、最大値を推測できません選択された値は、または関数がまったく使用されるかどうか)。私が考えることができる唯一のことは、すべてを静的ではなく、このメソッドを使用する必要がある各スレッドが独自の配列で Choose オブジェクトをインスタンス化することを主張することです。それは必要ではないようです。

末尾再帰を使用して C(n,k) を見つける関数をプログラムしたいのですが、助けていただければ幸いです。

私はこれに達しました：

二項係数の次のプロパティを使用します。

しかし、最後の命令が製品であるため、再帰呼び出しを各インスタンスによって実行される最後の命令にする方法がわかりません。唯一の方法だと思う補助機能を使って試してみましたが、解決策が見つかりませんでした。

私は無駄な単純な二項係数アルゴリズムを見つけようとして周りを見回してきました。問題は、私が授業に使用している言語が少し...奇妙なことです。その多くはYaccとLexを使用しています。

とにかく、クラスで例を示しました。

これは階乗の計算の例でしたが、C（n、k）またはNを計算できるように変更する必要があります。K（別名二項係数）を選択しますが、それほど複雑にする必要はありません。任意のNとKを選択できるため（ユーザーはそれらを入力する必要はありません）、任意の2つの乱数が機能します（上記の例のように）。このコードはwhileループや基本的な数学などの基本的な関数しかサポートしていないと確信しているので、階乗を使用することはできないと思います...しかし、上記のコードをそのまま使用できると思いますか？

何か案は？

「単純な」質問です。二項係数を計算する最速の方法は何ですか? - いくつかのスレッド化されたアルゴリズム?

私はヒントを探しています:)-実装ではありません:)

ブラケットをnの累乗に展開する関数をMATLABで作成しようとしています。ここで、nは自然数です。これは私がこれまでに持っているものです：

実行すると、次のエラーが発生します。

では、2つの変数を配列に格納するにはどうすればよいですか？

この問題を理解するのに問題があります。これは、一意でない文字のセットを組み合わせるのと似ていますが、少し異なります。

k、m、およびnを正の整数とします。nm個のボール、m個の色、n個のボール、およびk個の一意にラベル付けされたビンがあります。k個のバッグに入れるn個のボールを選択する方法はいくつありますか？

たとえば、m = 3、n = k = 2の場合、結果は21になります。2つのビンに配置するために合計6つから2つのボールを選択する3つの色があります。

（-、WW）、（-、WR）、（-、WB）..。

（WW、-）、（WR、-）..。

（W、W）、（W、R）..。

（B、W）、（B、R）..。

この問題の通常のバージョンでは、要素全体のサブセットを選択する必要はありません。その問題はnをもたらします！/ x ₁！x ₂！x ₃！...ここで、x ₁、x ₂、x3は重複した文字のグループです_。

修正（明確さ）->合計nmのボールがあります。m色ある各色のn個のボール。ここから、これらの合計nmボールのn個をランダムに選択し、k個の異なるビンに配置します。

ビデオゲームのキャラクターのアイテムビルドを把握するために、javascript でアプリを作成しています。上位アイテムは約25個あり、一度に6個運ぶことができます。効果が大きく異なるので、単体ではあまり良くないように見えても、他のアイテムと組み合わせると非常に強力になると私は信じています。興味があれば詳しく説明します。

質問:

1. 6 つのアイテムの異なる組み合わせすべてのリストを取得するにはどうすればよいですか? 組み合わせは何通りあるでしょう？25c6 (~134k) だけですか? または、重複を削除する必要がありますか? （すみません、しばらく数学の授業を休んでいました。）

2. このようなものをJavascriptでどのように実装しますか? これを行うことができる数学ライブラリはすでにありますか? (具体的には、アイテムの可能なすべての組み合わせを繰り返します。)

3. 考えられるすべての組み合わせのダメージを力ずくで計算し、最上位のアイテムの組み合わせを保存することは可能でしょうか? そうでない場合、強い組み合わせを見つけるためのより良いアルゴリズムはありますか?

みんなの入力に基づいた私のコードは次のとおりです。