Рассчитать N-ую комбинацию мультимножеств (с повторениями) только на основе индекса
Как я могу рассчитать 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 в (n+k-1)!/(k!(n-1)!) где K=5,
Вероятно, есть способ использовать эту информацию, чтобы определить точную комбинацию для произвольного индекса, не перечисляя весь набор, но я не уверен, нужно ли мне заходить так далеко. Первоначальная проблема заключалась в том, чтобы просто разложить полное комбо-пространство на равные подмножества, которые могут быть сгенерированы локально и работать параллельно с графическим процессором. Таким образом, вышеприведенный треугольник дает нам начальный индекс каждого блока, из которого тривиально может быть получена комбинация, и все ее последующие элементы постепенно нумеруются. Это также дает нам размер блока и сколько у нас всего комбинаций. Таким образом, теперь возникает проблема упаковки, состоящей в том, как распределить блоки неравномерного размера в группы с одинаковой рабочей нагрузкой на количество потоков X.
3 ответа
Смотрите пример по адресу: https://en.wikipedia.org/wiki/Combinatorial_number_system
Просто замените биномиальный коэффициент на (n+k-1)!/(k!(n-1)!),
Если предположить, n=3,k=5Допустим, мы хотим вычислить 19-ю комбинацию (id=19).
id=0, {0,0,0,0,0}
id=1, {0,0,0,0,1}
id=2, {0,0,0,0,2}
...
id=16, {1,1,1,1,2}
id=17, {1,1,1,2,2}
id=18, {1,1,2,2,2}
id=19, {1,2,2,2,2}
id=20, {2,2,2,2,2}
Результат, который мы ищем {1,2,2,2,2},
Изучая наш треугольник "Т2": n=3,k=5 указывает на 21, являясь пятым числом (сверху вниз) третьей диагонали (слева направо).
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
Нам нужно найти наибольшее число в этом ряду (по горизонтали, а не по диагонали), которое не превышает нашего id=19 значение. Так что двигаясь влево от 21 мы приходим к 6 (эта операция выполняется largest функция ниже). поскольку 6 2-й номер в этом ряду соответствует n==2 (или же g[2,5] == 6 из кода ниже).
Теперь, когда мы нашли 5-е число в комбинации, мы поднимаемся на пол в пирамиде, так что k-1=4, Мы также вычитаем 6 мы столкнулись ниже от id, так id=19-6=13, Повторяя весь процесс, мы находим 5 (n==2 снова) быть наибольшим числом меньше 13 в этом ряду.
Следующий: 13-5=8Самый большой 4 в этом ряду (n==2 еще раз).
Следующий: 8-4=4Самый большой 3 в этом ряду (n==2 еще раз).
Следующий: 4-3=1Самый большой 1 в этом ряду (n==1)
Таким образом, собирая индексы на каждом этапе, мы получаем {1,2,2,2,2}
Следующий код Mathematica делает работу:
g[n_, k_] := (n + k - 1)!/(k! (n - 1)!)
largest[i_, nn_, kk_] := With[
{x = g[nn, kk]},
If[x > i, largest[i, nn-1, kk], {nn,x}]
]
id2combo[id_, n_, 0] := {}
id2combo[id_, n_, k_] := Module[
{val, offset},
{val, offset} = largest[id, n, k];
Append[id2combo[id-offset, n, k-1], val]
]
Обновление: порядок создания комбинаций MBnext_multicombination не соответствует id2comboТак что я не думаю, что они были лексикографическими. Функция ниже генерирует их в том же порядке, что и id2combo и соответствует порядку математики Sort[]функция в списке списков.
void next_combo(unsigned int *ar, unsigned int n, unsigned int k)
{
unsigned int i, lowest_i;
for (i=lowest_i=0; i < k; ++i)
lowest_i = (ar[i] < ar[lowest_i]) ? i : lowest_i;
++ar[lowest_i];
i = (ar[lowest_i] >= n)
? 0 // 0 -> all combinations have been exhausted, reset to first combination.
: lowest_i+1; // _ -> base incremented. digits to the right of it are now zero.
for (; i<k; ++i)
ar[i] = 0;
}
Вот реализация комбинаторной системы счисления , которая обрабатывает комбинации с повторением и без него (т. е. мультимножество) и может дополнительно производить лексикографическое упорядочение.
/// Combinatorial number system encoder/decoder
/// https://en.wikipedia.org/wiki/Combinatorial_number_system
struct CNS(
/// Type for packed representation
P,
/// Type for one position in unpacked representation
U,
/// Number of positions in unpacked representation
size_t N,
/// Cardinality (maximum value plus one) of one position in unpacked representation
U unpackedCard,
/// Produce lexicographic ordering?
bool lexicographic,
/// Are repetitions representable? (multiset support)
bool multiset,
)
{
static:
/// Cardinality (maximum value plus one) of the packed representation
static if (multiset)
enum P packedCard = multisetCoefficient(unpackedCard, N);
else
enum P packedCard = binomialCoefficient(unpackedCard, N);
alias Index = P;
private P summand(U value, Index i)
{
static if (lexicographic)
{
value = cast(U)(unpackedCard-1 - value);
i = cast(Index)(N-1 - i);
}
static if (multiset)
value += i;
return binomialCoefficient(value, i + 1);
}
P pack(U[N] values)
{
P packed = 0;
foreach (Index i, value; values)
{
static if (!multiset)
assert(i == 0 || value > values[i-1]);
else
assert(i == 0 || value >= values[i-1]);
packed += summand(value, i);
}
static if (lexicographic)
packed = packedCard-1 - packed;
return packed;
}
U[N] unpack(P packed)
{
static if (lexicographic)
packed = packedCard-1 - packed;
void unpackOne(Index i, ref U r)
{
bool checkValue(U value, U nextValue)
{
if (summand(nextValue, i) > packed)
{
r = value;
packed -= summand(value, i);
return true;
}
return false;
}
// TODO optimize: (rolling product / binary search / precomputed tables)
// TODO optimize: don't check below N-i
static if (lexicographic)
{
foreach_reverse (U value; 0 .. unpackedCard)
if (checkValue(value, cast(U)(value - 1)))
break;
}
else
{
foreach (U value; 0 .. unpackedCard)
if (checkValue(value, cast(U)(value + 1)))
break;
}
}
U[N] values;
static if (lexicographic)
foreach (Index i, ref r; values)
unpackOne(i, r);
else
foreach_reverse (Index i, ref r; values)
unpackOne(i, r);
return values;
}
}
Полный код: https://gist.github.com/CyberShadow/67da819b78c5fd16d266a1a3b4154203
Я сделал предварительный анализ по этой проблеме. Прежде чем говорить о неэффективном решении, которое я нашел, позвольте мне дать вам ссылку на статью, которую я написал о том, как преобразовать k-индексы (или комбинации) в ранг или лексикографический индекс в комбинации, связанные с биномиальным коэффициентом:
http://tablizingthebinomialcoeff.wordpress.com/
Я начал так же, пытаясь решить эту проблему. Я придумал следующий код, который использует один цикл для каждого значения k в формуле (n+k-1)!/ K!(N-1)! когда k = 5. Как написано, этот код будет генерировать все комбинации для случая n, выберите 5:
private static void GetCombos(int nElements)
{
// This code shows how to generate all the k-indexes or combinations for any number of elements when k = 5.
int k1, k2, k3, k4, k5;
int n = nElements;
int i = 0;
for (k5 = 0; k5 < n; k5++)
{
for (k4 = k5; k4 < n; k4++)
{
for (k3 = k4; k3 < n; k3++)
{
for (k2 = k3; k2 < n; k2++)
{
for (k1 = k2; k1 < n; k1++)
{
Console.WriteLine("i = " + i.ToString() + ", " + k5.ToString() + " " + k4.ToString() +
" " + k3.ToString() + " " + k2.ToString() + " " + k1.ToString() + " ");
i++;
}
}
}
}
}
}
Результат этого метода:
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
Это те же значения, которые вы указали в отредактированном ответе. Я также попробовал это с 4 выберите 5, и, похоже, он генерирует правильные комбинации.
Я написал это на C#, но вы должны быть в состоянии использовать его с другими языками, такими как C/C++, Java или Python без слишком большого количества правок.
Одна идея для несколько неэффективного решения состоит в том, чтобы модифицировать GetCombos, чтобы также принимать k в качестве входных данных. Поскольку k ограничено 6, тогда можно было бы провести проверку на k. Таким образом, код для генерации всех возможных комбинаций для случая n select k будет выглядеть следующим образом:
private static void GetCombos(int k, int nElements)
{
// This code shows how to generate all the k-indexes or combinations for any n choose k, where k <= 6.
//
int k1, k2, k3, k4, k5, k6;
int n = nElements;
int i = 0;
if (k == 6)
{
for (k6 = 0; k6 < n; k6++)
{
for (k5 = 0; k5 < n; k5++)
{
for (k4 = k5; k4 < n; k4++)
{
for (k3 = k4; k3 < n; k3++)
{
for (k2 = k3; k2 < n; k2++)
{
for (k1 = k2; k1 < n; k1++)
{
Console.WriteLine("i = " + i.ToString() + ", " + k5.ToString() + " " + k4.ToString() +
" " + k3.ToString() + " " + k2.ToString() + " " + k1.ToString() + " ");
i++;
}
}
}
}
}
}
}
else if (k == 5)
{
for (k5 = 0; k5 < n; k5++)
{
for (k4 = k5; k4 < n; k4++)
{
for (k3 = k4; k3 < n; k3++)
{
for (k2 = k3; k2 < n; k2++)
{
for (k1 = k2; k1 < n; k1++)
{
Console.WriteLine("i = " + i.ToString() + ", " + k5.ToString() + " " + k4.ToString() +
" " + k3.ToString() + " " + k2.ToString() + " " + k1.ToString() + " ");
i++;
}
}
}
}
}
}
else if (k == 4)
{
// One less loop than k = 5.
}
else if (k == 3)
{
// One less loop than k = 4.
}
else if (k == 2)
{
// One less loop than k = 3.
}
else
{
// k = 1 - error?
}
}
Итак, теперь у нас есть метод, который будет генерировать все интересующие комбинации. Но проблема состоит в том, чтобы получить конкретную комбинацию из лексикографического порядка или ранга того, где эта комбинация находится внутри множества. Таким образом, это может быть выполнено простым подсчетом и возвращением правильной комбинации, когда она достигает указанного значения. Таким образом, чтобы учесть это, в метод необходимо добавить дополнительный параметр, представляющий ранг. Итак, новая функция для этого выглядит так:
private static int[] GetComboOfRank(int k, int nElements, int Rank)
{
// Gets the combination for the rank using the formula (n+k-1)!/k!(n-1)! where k <= 6.
int k1, k2, k3, k4, k5, k6;
int n = nElements;
int i = 0;
int[] ReturnArray = new int[k];
if (k == 6)
{
for (k6 = 0; k6 < n; k6++)
{
for (k5 = 0; k5 < n; k5++)
{
for (k4 = k5; k4 < n; k4++)
{
for (k3 = k4; k3 < n; k3++)
{
for (k2 = k3; k2 < n; k2++)
{
for (k1 = k2; k1 < n; k1++)
{
if (i == Rank)
{
ReturnArray[0] = k1;
ReturnArray[1] = k2;
ReturnArray[2] = k3;
ReturnArray[3] = k4;
ReturnArray[4] = k5;
ReturnArray[5] = k6;
return ReturnArray;
}
i++;
}
}
}
}
}
}
}
else if (k == 5)
{
for (k5 = 0; k5 < n; k5++)
{
for (k4 = k5; k4 < n; k4++)
{
for (k3 = k4; k3 < n; k3++)
{
for (k2 = k3; k2 < n; k2++)
{
for (k1 = k2; k1 < n; k1++)
{
if (i == Rank)
{
ReturnArray[0] = k1;
ReturnArray[1] = k2;
ReturnArray[2] = k3;
ReturnArray[3] = k4;
ReturnArray[4] = k5;
return ReturnArray;
}
i++;
}
}
}
}
}
}
else if (k == 4)
{
// Same code as in the other cases, but with one less loop than k = 5.
}
else if (k == 3)
{
// Same code as in the other cases, but with one less loop than k = 4.
}
else if (k == 2)
{
// Same code as in the other cases, but with one less loop than k = 3.
}
else
{
// k = 1 - error?
}
// Should not ever get here. If we do - it is some sort of error.
throw ("GetComboOfRank - did not find rank");
}
ReturnArray возвращает комбинацию, связанную с рангом. Итак, этот код должен работать для вас. Тем не менее, это будет намного медленнее, чем то, что может быть достигнуто, если будет выполнен поиск в таблице. Проблема с 300 выбрать 6 заключается в том, что:
300 choose 6 = 305! / (6!(299!) = 305*304*303*302*301*300 / 6! = 1,064,089,721,800
Это, вероятно, слишком много данных для хранения в памяти. Итак, если бы вы могли получить n до 20 с помощью предварительной обработки, то вы бы смотрели в общей сложности:
20 choose 6 = 25! / (6!(19!)) = 25*24*23*22*21*20 / 6! = 177,100
20 choose 5 = 24! / (5!(19!)) = 24*23*22*21,20 / 5! = 42,504
20 choose 4 = 23! / (4!(19!)) = 23*22*21*20 / 4! = 8,855
20 choose 3 = 22! / (3!(19!)) = 22*21*20 / 3! = 1,540
20 choose 2 = 21! / (2!(19!)) = 22*21 / 2! = 231
=======
230,230
Если для каждого значения комбинации используется один байт, то общее количество байтов, используемых для хранения таблицы (через зубчатый массив или, возможно, 5 отдельных таблиц) в памяти, может быть рассчитано как:
177,100 * 6 = 1,062,600
42,504 * 5 = 212,520
8,855 * 4 = 35,420
1,540 * 3 = 4,620
231 * 2 = 462
=========
1,315,622
Это зависит от целевой машины и объема доступной памяти, но 1 315 622 байта - это не так много памяти, когда сегодня на многих машинах имеется гигабайт доступной памяти.