Как я могу вычислить N-ю комбинацию, основываясь только на ней?индекс s. Должны быть (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

Обновить:

Так что я думал, что яd заменить биномиальный коэффициент в треугольнике Паскаля на(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 в(n+k-1)!/(k!(n-1)!) где .K=5

Вероятно, есть способ использовать эту информацию, чтобы определить точную комбинацию для произвольного индекса, не перечисляя весь набор, но яЯ не уверен, что мне нужно идти так далеко. Первоначальная проблема заключалась в том, чтобы просто разложить полное комбо-пространство на равные подмножества, которые могут быть сгенерированы локально и работать параллельно с графическим процессором. Таким образом, вышеприведенный треугольник дает нам начальный индекс каждого блока, из которого тривиально может быть получена комбинация, и все ее последующие элементы постепенно нумеруются. Это также дает нам размер блока и сколько у нас всего комбинаций. Таким образом, теперь возникает проблема упаковки, состоящей в том, как распределить блоки неравномерного размера в группы с одинаковой рабочей нагрузкой на количество потоков X.