インデックスのみに基づいて N 番目のコンボを計算するにはどうすればよいですか。(n+k-1)!/(k!(n-1)!) の組み合わせと繰り返しがあるはずです。
with n=2, k=5 you get:
0|{0,0,0,0,0}
1|{0,0,0,0,1}
2|{0,0,0,1,1}
3|{0,0,1,1,1}
4|{0,1,1,1,1}
5|{1,1,1,1,1}
したがって、black_magic_function(3) は {0,0,1,1,1} を生成する必要があります。
これは GPU シェーダーに入るので、シーケンスをグローバルに保存することなく、各ワークグループ/スレッドが順列のサブセットを把握できるようにしたいと考えています。
with n=3, k=5 you get:
i=0, {0,0,0,0,0}
i=1, {0,0,0,0,1}
i=2, {0,0,0,0,2}
i=3, {0,0,0,1,1}
i=4, {0,0,0,1,2}
i=5, {0,0,0,2,2}
i=6, {0,0,1,1,1}
i=7, {0,0,1,1,2}
i=8, {0,0,1,2,2}
i=9, {0,0,2,2,2}
i=10, {0,1,1,1,1}
i=11, {0,1,1,1,2}
i=12, {0,1,1,2,2}
i=13, {0,1,2,2,2}
i=14, {0,2,2,2,2}
i=15, {1,1,1,1,1}
i=16, {1,1,1,1,2}
i=17, {1,1,1,2,2}
i=18, {1,1,2,2,2}
i=19, {1,2,2,2,2}
i=20, {2,2,2,2,2}
MBnext_multicombinationそれを生成するためのアルゴリズムは、http://www.martinbroadhurst.com/combinatorial-algorithms.htmlで見ることができます。
アップデート：
それで、パスカルの三角形の二項係数を に置き換えて、(n+k-1)!/(k!(n-1)!)それがどのように見えるかを確認したいと思いました。
(* Mathematica code to display pascal and other triangle *)
t1 = Table[Binomial[n, k], {n, 0, 8}, {k, 0, n}];
t2 = Table[(n + k - 1)!/(k! (n - 1)!), {n, 0, 8}, {k, 0, n}];
(*display*)
{Row[#, "\t"]} & /@ t1 // Grid
{Row[#, "\t"]} & /@ t2 // Grid
T1:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
T2:
Indeterminate
1 1
1 2 3
1 3 6 10
1 4 10 20 35
1 5 15 35 70 126
1 6 21 56 126 252 462
1 7 28 84 210 462 924 1716
1 8 36 120 330 792 1716 3432 6435
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 個のスレッドにわたって作業負荷が等しいグループにどのように適合させるかというパッキングの問題になります。