問題タブ [binomial-coefficients]

C＃では、さまざまなインデックスのリストを含むリスト配列を作成しました。異なるインデックスの2つの組み合わせの1つの組み合わせを表示したいと思います。1つの中の2つの組み合わせを繰り返さないでください。

ペアになっている14人のプレーヤーでテニストーナメントをコーディングしようとしています。各プレーヤーは、他のプレーヤーと2回ペアリングしてはなりません。

更新：C（n、k）はBinomial Coefficient

私は数論の問題を扱っています。私は大きな問題を単純な問題に変換しました： 計算方法C(n,k)%3、n <= 10^15。1秒m ( <= 10 000 )以内に計算するために必要なデータセットについてあります。

私がそれを解決する方法は、を使用することですLucas' theorem。ですO(m log n)。そして、それは問題を解決するのに十分速いです。しかし、私はこの問題に対するより良い解決策があるかどうか、さらにはn <= 10^100それともm <= 1 000 000？

どうもありがとう！

dp を使用して c で ncr(combinations) を計算しようとしています。しかし、n=70 で失敗しています。誰でも助けることができますか？

基本的な考え方は ncr = ((n-r+1)/r)* nc(r-1) です

パスカルの三角形のn番目の行（特定の要素ではなく、行全体）を見つけることに興味があります。それを行うための最も効率的な方法は何でしょうか？

私は、上の行の対応する要素を合計することによって三角形を構築する従来の方法について考えました。

別の方法は、特定の要素の組み合わせ式を使用することです。

行の各要素については、組み合わせの計算方法によっては、前者の方法の方が時間がかかると思います。何か案は？

各試行の確率が同じであるPythonで標準的な二項分布を行う方法を知っています。私の質問は、試行確率が毎回変わる場合にどうするかです。私は以下の論文に基づいてアルゴリズムを起草していますが、標準的な方法が既にあるかどうかを確認するためにここをチェックする必要があると考えました.

http://www.tandfonline.com/doi/abs/10.1080/00949658208810534#.UeVnWT6gk6w

前もって感謝します、

ジェームズ

インデックスのみに基づいて N 番目のコンボを計算するにはどうすればよいですか。(n+k-1)!/(k!(n-1)!) の組み合わせと繰り返しがあるはずです。

したがって、black_magic_function(3) は {0,0,1,1,1} を生成する必要があります。

これは GPU シェーダーに入るので、シーケンスをグローバルに保存することなく、各ワークグループ/スレッドが順列のサブセットを把握できるようにしたいと考えています。

MBnext_multicombinationそれを生成するためのアルゴリズムは、http://www.martinbroadhurst.com/combinatorial-algorithms.htmlで見ることができます。

アップデート：

それで、パスカルの三角形の二項係数を に置き換えて、(n+k-1)!/(k!(n-1)!)それがどのように見えるかを確認したいと思いました。

T1:

T2:

n=3,k=5この記事の最初のコンソール出力と比較すると、3 番目の対角線{3,6,10,15,21,28,36}は各ロールオーバー ポイントのインデックス{0,0,0,1,1} -> {0,0,1,1,1} -> {0,1,1,1,1}などを示します。その左側の対角線は、前のブロックに含まれる値の数を示しているようです ( diagonal[2][i] == diagonal[3][i] - diagonal[3][i-1]))。(n+k-1)!/(k!(n-1)!)そして、ピラミッドの ​​5 行目を水平方向に読み取ると、 whereの N の値を増やすための組み合わせの最大数が得られますK=5。

セット全体を列挙することなく、この情報を使用して任意のインデックスの正確なコンボを決定する方法はおそらくありますが、そこまでする必要があるかどうかはわかりません。元の問題は、完全なコンボ スペースを等しいサブセットに分解することでした。これは、ローカルで生成され、GPU によって並行して処理されます。したがって、上の三角形はすべてのブロックの開始インデックスを示しており、そのコンボは自明に導出でき、その連続するすべての要素が増分的に列挙されます。また、ブロック サイズと、組み合わせの合計数もわかります。そのため、不均一なサイズのブロックを、X 個のスレッドにわたって作業負荷が等しいグループにどのように適合させるかというパッキングの問題になります。

nCr mod p効率的に計算する必要があります。今、このコードを書きましたが、制限時間を超えています。より最適なソリューションを提案してください。

私の場合、p = 10^9 + 7 and 1 ≤ n ≤ 100000000

nCr mod p32 ビット整数に収まることが保証されているため、オーバーフローがないことも確認する必要がありn!ますが、制限を超える可能性があります。

PS : また、私のコードは完全に正しくない可能性があると思います。ただし、小さい場合nは正しく機能するようです。間違っていたら指摘してください！