Сейчас на форуме: jinoweb (+6 невидимых)

 [email protected] —› Программирование —› Вычисление необычной последовательности
Посл.ответ Сообщение


Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 18 мая 2018 11:09 · Поправил: Boostyq
· Личное сообщение · #1

Всем привет
Пытаюсь решить странную задачу, она не связана с реверсом вообще, и нигде не опубликована, я просто на нее наткнулась, пока реализовывала одну штуку
Она больше связана с математикой и алгоритмами
Имеется 16 элементов, которые распределены в 4 группах
Code:
  1. Группа1 - 0,1,2,3;
  2. Группа2 - 4,5,6,7;
  3. Группа3 - 8,9,a,b;
  4. Группа4 - c,d,e,f;

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

Самое сложное, что нужно чтобы последовательность генерировалась по индексу, например GenerateSequence(0) -> { 3, 8, 5, 12, 2, 13, 6, 11, 0, 7, 9, 14, 1, 10, 15, 4 } и т.п.
При этом мне неизвестно кол-во вариантов и реально ли сгенерировать ее по индексу (так нужно потому что это должно рассчитываться во время компиляции)
Можно разделить задачу на две части и генерировать левую колонку и правую часть раздельно
Левую часть решить можно так
Code:
  1. uint8_t GenerateLeftColumn(size_t index)
  2. {
  3.     const static uint8_t variants[24] = {
  4.          27,  29,  39,  45,  54,  57, // 1234, 1243, 1324, 1342, 1423, 1432
  5.          75,  78,  99, 108, 114, 121, // 2134, 2143, 2314, 2341, 2413, 2431
  6.         135, 141, 147, 156, 177, 180, // 3124, 3142, 3214, 3241, 3412, 3421
  7.         198, 201, 210, 216, 225, 228, // 4123, 4132, 4213, 4231, 4312, 4321
  8.     };
  9.     // 2 бита на каждую цифру
  10.     return variants[index];
  11. }

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

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




Ранг: 590.6 (!), 408thx
Активность: 0.360.18
Статус: Модератор

Создано: 18 мая 2018 11:30
· Личное сообщение · #2

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

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


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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.050.12
Статус: Участник

Создано: 18 мая 2018 11:44 · Поправил: kunix
· Личное сообщение · #3

То есть, 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 и т.д.
Нормальный компиллер должен все это вычислить без проблем.




Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 18 мая 2018 12:01 · Поправил: Boostyq
· Личное сообщение · #4

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

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




Ранг: 590.6 (!), 408thx
Активность: 0.360.18
Статус: Модератор

Создано: 18 мая 2018 13:26
· Личное сообщение · #5

Под "рандомь" я подразумевал перестановку элементов (shuffle), есичо.
Code:
  1. // для 4х4
  2. random_shuffle(col[0]);
  3. random_shuffle(col[1]);
  4. random_shuffle(col[2]);
  5. random_shuffle(col[3]);
  6. // для 3х4
  7. random_shuffle(row[0]);
  8. random_shuffle(row[1]);
  9. random_shuffle(row[2]);
  10. random_shuffle(row[3]);


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


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

Ранг: 71.2 (постоянный), 33thx
Активность: 0.050.12
Статус: Участник

Создано: 18 мая 2018 13:34 · Поправил: kunix
· Личное сообщение · #6

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


Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 18 мая 2018 15:55 · Поправил: Boostyq
· Личное сообщение · #7

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

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




Ранг: 54.0 (постоянный), 49thx
Активность: 0.721.1
Статус: Участник

Создано: 18 мая 2018 17:30
· Личное сообщение · #8

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



Ранг: 71.2 (постоянный), 33thx
Активность: 0.050.12
Статус: Участник

Создано: 18 мая 2018 18:46 · Поправил: kunix
· Личное сообщение · #9

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

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




Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 18 мая 2018 18:48 · Поправил: Boostyq
· Личное сообщение · #10

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

На самом деле нет
Кстати там не 429981696 во второй степени, вроде можно вот так
Code:
  1. for (size_t a = 0; a < 429981696; a++)
  2.          {
  3.                  for (size_t b = a + 1; b < 429981696; b++)
  4.                  {
  5.                         if (packed[a] == packed[b])
  6.                         {
  7.                               printf("[!!!] Collision found%zu (%llX) == %zu (%llX)\n", a, packed[a], b, packed[b]);
  8.                         }
  9.                  }
  10.          }

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

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

В uint64_t упаковку уже сделала, сейчас у меня просто выделяется память (3.6гб) и рассчитывается, это занимает минуту, а вот проверки уже очень долго

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


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


Ранг: 271.4 (наставник), 331thx
Активность: 0.321.49
Статус: Участник

Создано: 18 мая 2018 19:47 · Поправил: f13nd
· Личное сообщение · #11

Вариантов в первой колонке 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


Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 18 мая 2018 21:05
· Личное сообщение · #12

f13nd пишет:
мне одному в этой абстрактной задаче видится шулерская слот-машина

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

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





Ранг: 77.2 (постоянный), 74thx
Активность: 0.190.15
Статус: Участник

Создано: 18 мая 2018 21:30
· Личное сообщение · #13

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



Ранг: -0.7 (гость), 170thx
Активность: 0.540
Статус: Участник

Создано: 19 мая 2018 04:21
· Личное сообщение · #14

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

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

Ранг: 43.8 (посетитель), 16thx
Активность: 0.020.06
Статус: Участник

Создано: 19 мая 2018 21:29
· Личное сообщение · #15

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




Ранг: 90.1 (постоянный), 91thx
Активность: 0.290.56
Статус: Участник

Создано: 19 мая 2018 22:47 · Поправил: Boostyq
· Личное сообщение · #16

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

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



 [email protected] —› Программирование —› Вычисление необычной последовательности
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати