Как стать автором
Обновить

Комментарии 18

Факториальное разложение числа — бесполезный вредный слой абстракции в тривиальной задаче перебора пермутаций.

На самом деле, существует алгоритм прямой генерации следующей в лексикографическом порядке перестановки, и довольно простой.


  1. Идем с конца массива в поисках первого элемента, который будет меньше чем его сосед справа. Если такой не найден — значит, это была последняя перестановка.


  2. Находим правее найденного элемента минимальный среди тех, которые больше найденного (такой будет хотя бы 1).


  3. Меняем местами элемент, найденный на шаге 1, с элементом, найденным на шаге 2.


  4. Разворачиваем все элементы, которые правее позиции, найденной на шаге 1.

Этот алгоритм слишком простой чтобы вводить лишние абстракции вроде факториальной системы счисления. Кстати, в C++ он реализован в стандартной функции std::next_permutation

Вот круто. Спасибо!

Нужная вещь. В таблицах Google для ведения портфеля проектов иногда нужны все их возможные сочетания. Там JS (в таблицах), и я искал реализации перестановок, такого насмотрелся разного, что после — ваш алгоритм просто жутко предпочтителен.
И кстати, алгоритм Кнута (а это он) позволяет итеративно выполнять перестановки в наборах с повторениями.
Например, если взять набор из N-K нулей и K единиц, то он переберёт все сочетания из N по K.

Не знаю про алгоритм Кнута, я этот алгоритм написал независимо в школе :) Есть такие задачи, которые затруднительно решить принципиально разными способами.


Кстати, чтобы приведенный мною алгоритм действительно работал при наличии повторений — надо на шаге 2 искать самый правый из максимальных элементов.

А как распараллелить?

Получение следующего элемента или перебор всех? Первое невозможно, во втором случае генерируем промежуточные точки для сегментов другим алгоритмом, которые потом будут использоваться в качестве границ.


Для точной генерации промежуточных точек можно использовать алгоритм получения перестановки по номеру.

Итеративные алгоритмы перебора перестановок в лекcикографическом порядке распараллелить достаточно просто. Указывается точка начала и точка остановки для каждой части набора n.
Вспоминается картинка про троллейбус из буханки хлеба :) Хотя, с чисто исследовательской позиции — достаточно интересно.
А между тем движок хабра начал поддерживать LaTeX-нотацию для статей.

Для блочной формулы оборачиваем в $$display$$, для строчной — в $inline$.
$$display$$1966_{10} = 1\cdot10^3 + 9 \cdot 10^2 + 6 \cdot 10^1 + 6 \cdot10^0$$display$$


Кстати, подобная система счисления существует не только для весов разрядов 1!, 2!, 3! и так далее, но и для любых чисел: n1,  n1·n2,  n1·n2·n3,  n1·n2·n3·n4, …
О да, я этим пользовался, решая задачу по обфускации. Что-то типа такого:

Имя переменной должно начинаться с буквы, а дальше буквы, цифры и подчёркивания? Беру массив, где первые 26 (или 52 для case-sensitive, но тогда я этого не сообразил) — буквы, далее — десять цифр и подчёркивание. Беру номер переменной по порядку (они отсортированы по частоте употребления), и перевожу в систему счисления с основанием 26 в младшем разряде и 37 в следующих. По значению в разряде выбирается символ из массива, символы записываются от младшего разряда к старшему слева направо. Вуаля, идентификатор готов.
Что-то тут не так, но мне кажется long имеет разрядность 64 и его максимальная величина 9223372036854775807, а из этого следует что 13! туда помещается. Вы наверно спутали с int.

В Си/С++ на наиболее распространенных компиляторах long имеет разрядность 32 бита.

НЛО прилетело и опубликовало эту надпись здесь
тут https://youtu.be/DbEHomTt_7Q
алгоритм перестановок с возможностью остановки и продолжения в любом месте
для перебора паролей самое то. скорость в 5 раз выше рекурсии
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.