我如何仅根据它的索引计算第 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,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])）。如果您水平阅读金字塔的第 5 行，您将获得最大数量的组合，以增加 N in (n+k-1)!/(k!(n-1)!)where的值K=5。
可能有一种方法可以使用此信息来确定任意索引的确切组合，而无需枚举整个集合，但我不确定我是否需要走那么远。最初的问题只是将完整的组合空间分解为相等的子集，这些子集可以在本地生成，并由 GPU 并行处理。所以上面的三角形给了我们每个块的起始索引，其中的组合可以很简单地导出，并且它的所有连续元素都递增地枚举。它还为我们提供了块大小，以及我们拥有的总组合数。因此，现在如何将不均匀大小的块放入跨 X 个线程的相等工作负载组中成为一个打包问题。