Как я могу вычислить N-го комбо, основанного только на его индексе. Должны быть (n + k-1)!/(K! (N-1)!) Комбинации с повторениями.Рассчитать N-ю мультимножественную комбинацию (с повторением), основанную только на индексе
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}.
Это войдет в шейдер графического процессора, поэтому я хочу, чтобы каждая рабочая группа/нить была в состоянии определить их подмножество перестановок, не сохраняя последовательность в глобальном масштабе.
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
Update:
Так я думал, я бы заменить биномиальный коэффициент в Паскалях треугольнике с (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
Т1:
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
Т2:
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])). И если вы читаете пятый ряд пирамиды по горизонтали, вы получаете максимальное количество комбинаций для увеличения значений N в (n+k-1)!/(k!(n-1)!), где K=5.
Возможно, существует возможность использовать эту информацию для определения точной комбинации для произвольного индекса без перечисления всего набора, но я не уверен, что мне нужно зайти так далеко. Первоначальная проблема состояла в том, чтобы разложить полное комбо-пространство на равные подмножества, которые могут быть сгенерированы локально и параллельно работать с GPU. Таким образом, треугольник выше дает нам начальный индекс каждого блока, из которого комбо может быть тривиально выведено, и все его последующие элементы постепенно перечислимы. Он также дает нам размер блока и количество общих комбинаций. Итак, теперь проблема упаковки заключается в том, как размещать блоки с неравномерным размером в группы равной рабочей нагрузки по X количеству потоков.
Каковы максимальные значения для n и k? –
Максимальное значение K равно 6. Максимальное значение N не может превышать 300, но с некоторыми предварительными обработками можно свести куда-нибудь по линиям 20, 50 или 100. –
Итак, случай n = 2 довольно тривиальна - просто придерживайтесь столько, сколько указано k, начиная с правой и оставляйте остальных на нуле. Для случая n = 3, k = 5, я получаю (3 + 5-1)!/5! (3-1)! = 21. Но я не совсем уверен, как выглядят комбинации. Не могли бы вы отредактировать свой вопрос и показать комбинации для n = 3 и k = 5? –