Комментарии 18
На самом деле, существует алгоритм прямой генерации следующей в лексикографическом порядке перестановки, и довольно простой.
Идем с конца массива в поисках первого элемента, который будет меньше чем его сосед справа. Если такой не найден — значит, это была последняя перестановка.
Находим правее найденного элемента минимальный среди тех, которые больше найденного (такой будет хотя бы 1).
Меняем местами элемент, найденный на шаге 1, с элементом, найденным на шаге 2.
- Разворачиваем все элементы, которые правее позиции, найденной на шаге 1.
Этот алгоритм слишком простой чтобы вводить лишние абстракции вроде факториальной системы счисления. Кстати, в C++ он реализован в стандартной функции std::next_permutation
Нужная вещь. В таблицах Google для ведения портфеля проектов иногда нужны все их возможные сочетания. Там JS (в таблицах), и я искал реализации перестановок, такого насмотрелся разного, что после — ваш алгоритм просто жутко предпочтителен.
Например, если взять набор из N-K нулей и K единиц, то он переберёт все сочетания из N по K.
Не знаю про алгоритм Кнута, я этот алгоритм написал независимо в школе :) Есть такие задачи, которые затруднительно решить принципиально разными способами.
Кстати, чтобы приведенный мною алгоритм действительно работал при наличии повторений — надо на шаге 2 искать самый правый из максимальных элементов.
Получение следующего элемента или перебор всех? Первое невозможно, во втором случае генерируем промежуточные точки для сегментов другим алгоритмом, которые потом будут использоваться в качестве границ.
Для точной генерации промежуточных точек можно использовать алгоритм получения перестановки по номеру.
Для блочной формулы оборачиваем в $$display$$, для строчной — в $inline$.
$$display$$1966_{10} = 1\cdot10^3 + 9 \cdot 10^2 + 6 \cdot 10^1 + 6 \cdot10^0$$display$$
Имя переменной должно начинаться с буквы, а дальше буквы, цифры и подчёркивания? Беру массив, где первые 26 (или 52 для case-sensitive, но тогда я этого не сообразил) — буквы, далее — десять цифр и подчёркивание. Беру номер переменной по порядку (они отсортированы по частоте употребления), и перевожу в систему счисления с основанием 26 в младшем разряде и 37 в следующих. По значению в разряде выбирается символ из массива, символы записываются от младшего разряда к старшему слева направо. Вуаля, идентификатор готов.
алгоритм перестановок с возможностью остановки и продолжения в любом месте
для перебора паролей самое то. скорость в 5 раз выше рекурсии
Как перебрать все перестановки и о факториальном разложении натуральных чисел