Всем привет
Пытаюсь решить странную задачу, она не связана с реверсом вообще, и нигде не опубликована, я просто на нее наткнулась, пока реализовывала одну штуку
Она больше связана с математикой и алгоритмами
Имеется 16 элементов, которые распределены в 4 группах

Далее есть таблица 4 на 4, которая должна поместить в себя все элементы без повторений
Но из-за доп.условий все становится сложнее:
1) Первая группа всегда должна быть приклеена к левой колонке
2) Только один элемент из группы может быть в каждом ряду
Вот иллюстрация с примерами:

Самое сложное, что нужно чтобы последовательность генерировалась по индексу, например GenerateSequence(0) -> { 3, 8, 5, 12, 2, 13, 6, 11, 0, 7, 9, 14, 1, 10, 15, 4 } и т.п.
При этом мне неизвестно кол-во вариантов и реально ли сгенерировать ее по индексу (так нужно потому что это должно рассчитываться во время компиляции)
Можно разделить задачу на две части и генерировать левую колонку и правую часть раздельно
Левую часть решить можно так

Но для правой части выходит очень много вариантов, их точно меньше !12 (479001600) из-за вариантов с коллизиями, но их невозможно описать таблицей например
Хотя бы нужен алгоритм для генерации таблицы 3 на 4, из 12 элементов без повторений по индексу
Надеюсь здесь есть математики, которые могут подсказать
Заранее спасибо

-----
В облачке многоточия

| Сообщение посчитали полезным:

Независимо рандомь сначала каждую колонку, а потом построчно но без первой колонки.

-----
старый пень

| Сообщение посчитали полезным: sefkrd

То есть, GenerateSequence(idx) должна быть достаточно простой, чтобы компиллер смог ее вычислить?
Не вижу проблем.
В столбцах 2,3,4 каждой строки у вас будет по элементу из каждой группы 2,3,4 (группы идут в любом порядке).
Это 6 вариантов.
4 строки дают 6^4 вариантов.

Раскидав группы по клеткам, осталось выбрать конкретную перестановку каждой группы.
Перестановки элементов одной из групп дают 24 варианта.
Итого (6*24)^4 = 429981696.
Не влезло в 32 бита, ну и ладно.

Выбор каждого варианта делать по idx%6 или idx%24.
Потом делать idx = idx / 6 и т.д.
Нормальный компиллер должен все это вычислить без проблем.

| Сообщение посчитали полезным:

Возвращать итоговую таблицу можно в uint64_t как раз все 16 клеток влезают по 4 бита, для сида хватит uint32_t, однако как быть с коллизиями не знаю
Насчет 17915904 kunix был прав, я их попробовала перебрать, нужно где-то 136мб если хранить правую часть в файле например, но вроде нельзя через constexpr читать файлы

-----
В облачке многоточия

| Сообщение посчитали полезным:

Под "рандомь" я подразумевал перестановку элементов (shuffle), есичо.


-----
старый пень

| Сообщение посчитали полезным: Boostyq, kunix

Boostyq, можно попробовать через constexpr или шаблоны.
Но я говорил про более простую вещь.
Написать функцию типа GenerateLeftColumn(), но конечно более сложную.
Нормальный компилятор вызов GenerateLeftColumn() вычислит полностью.
У меня старенький MSVC шифрует строки и инлайнит их посимвольную и сборку расшифровку в место вызова.

Фактически вам надо что-то типа:

char permutation4[4];
char permutation3[3];

GetPermutation4(idx%24, permutation4);
idx = idx / 24;

GetPermutation3(idx%6, permutation3);
idx = idx / 6;

arr[row*4 + permutation3[i] + 1] = permutation4[j];

Все это должно вычислиться на этапе компиляции. Я думаю, это возможно.

GetPermutation4 и GetPermutation3 - просто табличные функции как GenerateLeftColumn.

| Сообщение посчитали полезным: Boostyq

Что-то наляпала, но какое-то некачественное перемешивание выходит, хотя я все что можно уже перемешала
kunix и r_e большое спасибо, потому что идея с перемешиванием мне даже в голову не приходила
Сейчас пытаюсь выполнить проверку на коллизии (просто я не уверена, что у меня нет ошибок), но идет очень долго, 429981696 во второй степени итераций, тут нужен ботнет

-----
В облачке многоточия

| Сообщение посчитали полезным:

да вы и сами лучще нас разбираетесь

| Сообщение посчитали полезным:

r_e умеет по-простому объяснять .

Перебор 2^64 - это по сложности как meet-in-the-middle атака на MD5.
Вы правда собрались это делать?
Нормальный способ - закодировать всё в uint64_t, сгенерить все uint64_t в файл (~32GB), отсортировать через merge sort, сравнить соседние.
Сложность - 64*2^32.

| Сообщение посчитали полезным:

SDK пишет:
да вы и сами лучще нас разбираетесь
На самом деле нет
Кстати там не 429981696 во второй степени, вроде можно вот так

в теории должно чем меньше осталось - тем быстрее работать, но даже так не удалось и процента пройти, так что забила
Наверное еще можно через CUDA сделать, тогда возможно удастся пройти целиком, но пока не буду заморачиваться
Кстати если кому-то вдруг нужен код могу выложить

kunix пишет:
Перебор 2^64 - это по сложности как meet-in-the-middle атака на MD5.
Вы правда собрались это делать?
Нормальный способ - закодировать все в uint64_t, сгенерить все uint64_t в файл, отсортировать через merge sort, сравнить соседние.
Сложность - 64*2^32.
В uint64_t упаковку уже сделала, сейчас у меня просто выделяется память (3.6гб) и рассчитывается, это занимает минуту, а вот проверки уже очень долго

-----
В облачке многоточия

| Сообщение посчитали полезным: SDK

Вариантов в первой колонке 4*3*2*1 (все комбинации элементов 1й группы, на первой позиции возможно 4 варианта, на второй на 1 меньше и т.д.)
Далее есть 4 ряда по 3 элемента, в каждом из которых не может быть двух элементов из 3 оставшихся групп, то есть в каждом ряду по 1 элементу из 3 оставшихся групп
первый ряд правой части: (4*3)*(4*2)*(4*1)
второй ряд (3*3)*(3*2)*(3*1)
третий ряд (2*3)*(2*2)*(2*1)
четвертый ряд 1 комбинация

итого 4*3*2*1*4*3*4*2*4*1*3*3*3*2*3*1*2*3*2*2*2*1=71663616 комбинаций, если калькулятор не врет.

первый столбец можно кодировать 2мя,2мя и 1м битами:
1.00,01,10,11 это 1,2,3 или 4 элемент 1 группы соотвественно
2.00,01,10 один из оставшихся трех, комбинация 11 запрещенная, проверять битовой маской и пропускать все комбинации, где будут эти 2 единицы
3.0,1 один из двух оставшихся
4.последний
итого 5 бит

Ну и с 4 рядами по аналогии. Вводишь счетчик из нужного количества бит, накручиваешь на 1, проверяя и пропуская запрещенные состояния, по нему раскодируешь всю комбинацию как показано выше. Таким образом можно получить искомую функцию.

ЗЫ: по-моему накосячил с расчетами, но не суть. первый элемент каждого ряда 2 бита для выбора одной из 3 групп, 2 бита на выбор элемента в ней, далее 1 бит на выбор из 2 оставшихся групп и 2 на выбор элемента, и еще 2 для выбора элемента оставшейся группы. Второй ряд тоже 2+2, 1+2, 2, третий 1+1, 1+1, 1, четвертый ряд ничего уже подбирать не остается. 28 чтоли бит получилось, просто их перебрать у компуцера займет меньше секунды, с проверкой запрещенных состояний чуть подольше, функцией можно отсчитать нужное количество разрешенных и раскодировать результат. Никаких гигабайт памяти и часов расчетов тут по идее быть не должно.
ЗЗЫ: мне одному в этой абстрактной задаче видится шулерская слот-машина?

-----
2 оттенка серого

| Сообщение посчитали полезным: Boostyq

f13nd пишет:
мне одному в этой абстрактной задаче видится шулерская слот-машина
Я честно говоря не знаю, что это такое
Этот алгоритм нужен мне для личной задачи, не связано с коммерцией

-----
В облачке многоточия

| Сообщение посчитали полезным:

Копать в сторону матриц..
Так сложно пишут о простом..

| Сообщение посчитали полезным:

В google - permutation matrix, на SO полно реализаций.

| Сообщение посчитали полезным: Boostyq

Это вам про конечные поля Галуа надо почитать.

| Сообщение посчитали полезным:

Всем большое спасибо
Наверняка есть методы умнее, но я реализовала через перемешивание, как сказали выше
Вообще это всего лишь маленькая задача по метаморфному мутированию, и так уже слишком сложно вышло
Да и на большее меня не хватит, и так от матана крыша едет

-----
В облачке многоточия

| Сообщение посчитали полезным: