Порождение перестановок, имеющих ограничения (with constraints)

Тема громкая, но трудная, и я не претендую на полный охват. Начало было положено вопросом DimaT в известном некоторым топике о том, как ускорить цикл
do{ ... }while( next_permuts(....)) .

Тема естественным образом распадается на 3 варианта:
1) не влезая внутрь next_permuts()
2) влезя или используя свою
3) для чего это нужно.

Вопрос оказался интересным,особенно (2-3). Я кратко напишу потом свои думки и что нарыл. Ну и кому есть что сказать по теме топика, тоже пишите, пожалуйста.

Чтоб увернуться от помидоров, прикладываю С++ исходник - как есть, т.е. с разной грязью.
Грязь в виде лишних переменных, закомеченных строк, иногда кривых комментариев, актуальных в VBA.
Т.к. прога берёт начало аж от VBS-скрипта, отлажена в эксэл-вба, и только потом переложена на Си.
Отсутствует Си-шная оптимизация. Есть некоторая алгоритмическая оптимизация.
Это только начало.

Особенности проги.

+

Компилилось в minGW 6. В её ядре нет места "Classицизму". Прога формирует перестановки, используя родной next_permuts(....), к-рый порождает их в лексикографической послед-сти. Те из них, которые удовлетворяют заложенному ограничению, выводятся в stdout. Ограничение= правильное расположение в задаче о ферзях. Сидит в отдельной процедуре CheckPermuts2(). Запускать ЕХЕ так: main3.exe [14] [<in1] [>true14] - "14" - единственный используемый параметр в argv[], размерность задачи, по умолчанию переменная DLINA=4 - true14 - stdout - in1 - stdin На win64 время для 13 - 340сек, для 14 - 5000 сек, файл текстовый 24,3 Мб Поскольку для 15 придётся время умножить на 15, а диск на ..., то .... Небольшой тормоз представляет периодический сброс stdout на диск. Регулируется макросом FLUSH2DISK= 0xffffff - каждые ХХ перестановок. При долгой работе на диске файла долго не видно. Чтобы не накручивать показометр хода процесса, заставляю принудительно писать на диск. Так я могу мониторить время, а в тоталкоммандере и открыть файл он-лайн. Процедура, описанная в начале void my_atexit() { /*Paused to look at results ...*/ имеет цель, указанную в комментарии: перед выходом остановиться и посмотреть конечный резалт. По ENTERу заканчивавем. Если на stdin подать файл "in1" (любой, лучше пустой файл в текущем с ЕХЕ каталоге),то прога закончит без остановки в конце. И, как отмечал, не удивляйтесь VBAшным "For-Step-Next" и т.д., а загляните в начало, где они описаны как макросы.

Продолжение последует, но не сразу.

exp98,

а зачем отделять ограничения от процесса генерации?

Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!

Возможно я повторяю кого-либо.
Кзалось бы как ускорить перебор, не меняя функцию?
Но если нужна только их часть, обладающая общим свойством, то можно.
Имелось желание свести построение N-перестановок к декартовому поизведению К-перестановок, где К меньше N. Как писал выше, типа (Pn)=(Pn-k) х (Pk) и (Pk) - с нужными свойствами.

Это не означает рекурсивные вызовы.
- готовится (Pk) при n=k с той лишь разницей, что значения не в [1-k], а в [1-n]. И это не перестановки,а размещения (An,k). И они имеют заданное свойство в своей части
- затем каждая из них склеивается с (Pn-k) и проверяется на свойство.

Я просто посмотрел это на проге из начаала темы для к=3 и 4. Небольшая обвёртка, даже заведомо неоптимаизированная дал прибавку. Ускорение понятно, что за счёт сокращения общего кол-ва. Время работы ~ объёму перебора.
Было
13 - 340сек, для 14 - 5000 сек,
Стало
13 - 130сек, для 14 - 2000 сек
Нууу, 15 предположительно за ночь прогонится.

Непонятно, имеет ли смысл дробить мельче, чем k= n/2 ?
В случае свойства = "расстановка фишек" ?
В случае подбора пароля ?

exp98
Мне кажется, что это может пригодиться в реальных задачах. В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях. Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С), где В/C/или оба имеют нужные свойства, а ||A|| = N!

Почему вас не устраивает классический перебор с возвратом? Или существующие подходы к решению constraint satisfaction problem, где уже в постановке задачи вводят ограничения на каждую переменную

Потому что Вы про пункт (2), а я про п.(1) - т.е. не влезая внутрь готовой функции.
И потом, разве плохой метод ускорения? И я не настаиваю, что знаю всё на свете. И просто интерсно сравнить.

Хотел немного оправдаться. Выше я сравнивал варианты (Pn-k)x(An,k) при k=4, к тому же записью в файл.
Сравнил для k=5, без печати:

12/5, w/o print, time= 0.390001 s, Total= 84934080, 218 m/c
13/5, w/o print, time= 5.694010 s, Total= 1253952000, 220 m/c
14/5, w/o print, time= 88.311755 s, Total= 19620195840, 222 m/c

12/0, w/o print, time= 2.308804 s, Total= 479001600,  207.5 m/c
13/0, w/o print, time= 29,858453 s, Total= 6227020800, 208.5 m/c
14/0, w/o print, time= 414.898329 s, Total= 87178291200, 210 m/c

12,13,14 - размерность n
12/5 при k=5
12/0 при k=0,т.е. для (Pn)
Total - длина перебора
m/c - вычисленная производительность млн/сек

exp98
Мне кажется, что это может пригодиться в реальных задачах. В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях. Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С), где В/C/или оба имеют нужные свойства, а ||A|| = N!

Так использование ограничений в процессе генерации и позволяет сократить перебор (в общем виде это называется "метод ветвей и границ"),
НО в каждой задаче свои ограничения - вот и нужен не столько встроенны генератор,
сколько общий фрейм генератора, чтобы на разных этапах формирования очередного варианта была возможность добавлять ограничения, отсекающие непригодные варианты.

Я тоже думалл, что нужен (типа qsort). Почему-то его не видно - это раз. А так получилось проверить идею "квазибэктрекинга".
Второе - вопрос тогда, что будет быстрее работать: бэктрекинг, заточенный под задачу или этот универсальный? или тот, встроенный, или квази. Если "под задачу", то очевидно, что его самому реализовывать.

Чесгря успел забыть про тему, увы.
Я почитал про сплетение групп и полугрупп, как раз чтобы получать заданные св-ва либо, или если другими методами, то для реализации быстро вычисляемыми операциями.
Но за 3 подхода не смог полностью уяснить, что я делал - это тоже сплетение или нет. И огорчило, что не нашёл более детальных разработок про это.