n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1
Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000
Как видно, факториал 13-ти уже не умещается в тип данных long.
Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.
Для начала вспомним понятие позиционной системы счисления. Вклад каждого разряда числа в его значение в позиционной системе по основанию K есть разряд, умноженный на основание K в степени, равной позиции разряда в записи числа. Основание системы счисления обычно пишут как подстрочный индекс, таким образом
196610 = 1*103 + 9 * 102 + 6 * 101 + 6 (*100)
101100012 = 1 * 27 + 0 * 26 + 1 * 25 + 1 * 24 + 0 * 23 + 0 * 22 + 0 * 21 + 1 * 20 (=17710)
Позиционная запись, помимо компактности, обладает тем бесценным свойством, что алгоритм выполнения арифметических операций оказывается чрезвычайно простым (есть историческая байка, что в школах средневековья изучение арифметики занимало несколько лет, поскольку вычисления над числами в НЕпозиционной римской записи имели множество правил для того, чтобы провести простое сложение!)
Оказывается, существует, и является однозначным разложение и способ записи числа, в котором каждый разряд в таком его представлении умножается на ФАКТОРИАЛ номера позиции.
Покажем это на примерах:
1985 = 2 * 6! + 4 * 5! + 2 * 4! + 2 * 3! + 2 * 2! + 1 * 1!
2 940 861 129 405 = 2*15! + 3*14! + 10*13! + 3*12! + 6*11! + 8*10! + 4*9! + 8*8! + 0*7! + 2*6! + 2*5! + 1*4! + 3*3! + 1*2! + 1*1!
В обычной позиционной системе значение каждого разряда должно быть строго меньше основания. В факториальной же системе каждый «разряд» меньше либо равен основанию факториала, перед которым он стоит. При этом действуют обычные для сложения правила переноса разряда при переполнении.
Более математически строго: каждое натуральное число n можно единственным образом представить в виде следующей суммы:
где
km <= m – коэффициент при m! — он же разряд числа в его факториальном представлении,
p – количество «разрядов» в числе в его факториальном представлении
то есть число записывается как kp kp-1 kp-2… k2 k1
Теперь опишем, как использовать факториальное представление (разложение) числа для генерации соответствующей перестановки. Расположим n элементов в порядке возрастания индекса от 1 до n. Для каждого числа в диапазоне 0..n!-1 произведем факториальное разложение, вычислив его коэффициенты km. В разложении нуля коэффициенты km будут все нули, в разложении числа n!-1 все km = m, m меняется в диапазоне от 0 до n-1. Теперь поместим элемент с номером m на место с номером km+1, считая лишь свободные места, оставшиеся к этому шагу. Фактически, эта процедура повторяет рассуждения, которые приводятся при вычислении числа возможных перестановок из n элементов – первый элемент может быть размещен n способами, второй – (n-1) способом и так далее. Таким образом, мы получим все возможные перестановки из n несовпадающих элементов.
Проиллюстрируем это для 5 предметов (120 вариантов перестановок) и перестановки №77
77 = 3 * 4! + 0 * 3! + 2 * 2! + 1 * 1!
Не являясь программистом-практиком, я все же выскажу предположения (теоретические)), как можно было бы использовать подобное разложение. Можно разбить общее число возможных перестановок на поддиапазоны по числу имеющихся параллельных потоков исполнения, и извлекать текущую перестановку прямо из представления переменной цикла в факториальной записи. Разложение в факториальную форму – задача достаточно вычислительно сложная, но можно разложить только стартовое число поддиапазона, а затем просто прибавлять единицу, перенося ее в следующий разряд в случае переполнения.
Комментарии (17)
mayorovp
17.01.2017 08:55+7На самом деле, существует алгоритм прямой генерации следующей в лексикографическом порядке перестановки, и довольно простой.
Идем с конца массива в поисках первого элемента, который будет меньше чем его сосед справа. Если такой не найден — значит, это была последняя перестановка.
Находим правее найденного элемента минимальный среди тех, которые больше найденного (такой будет хотя бы 1).
Меняем местами элемент, найденный на шаге 1, с элементом, найденным на шаге 2.
- Разворачиваем все элементы, которые правее позиции, найденной на шаге 1.
Этот алгоритм слишком простой чтобы вводить лишние абстракции вроде факториальной системы счисления. Кстати, в C++ он реализован в стандартной функции std::next_permutation
S_A
17.01.2017 09:25+1Вот круто. Спасибо!
Нужная вещь. В таблицах Google для ведения портфеля проектов иногда нужны все их возможные сочетания. Там JS (в таблицах), и я искал реализации перестановок, такого насмотрелся разного, что после — ваш алгоритм просто жутко предпочтителен.
ShashkovS
17.01.2017 10:22+3Есть отличная книжка про такие штуки: А. Шень. Программирование: теоремы и задачи.
nickolaym
17.01.2017 13:24+3И кстати, алгоритм Кнута (а это он) позволяет итеративно выполнять перестановки в наборах с повторениями.
Например, если взять набор из N-K нулей и K единиц, то он переберёт все сочетания из N по K.mayorovp
17.01.2017 13:50+1Не знаю про алгоритм Кнута, я этот алгоритм написал независимо в школе :) Есть такие задачи, которые затруднительно решить принципиально разными способами.
Кстати, чтобы приведенный мною алгоритм действительно работал при наличии повторений — надо на шаге 2 искать самый правый из максимальных элементов.
vkomen
17.01.2017 10:19А как распараллелить?
mayorovp
17.01.2017 10:25+1Получение следующего элемента или перебор всех? Первое невозможно, во втором случае генерируем промежуточные точки для сегментов другим алгоритмом, которые потом будут использоваться в качестве границ.
Для точной генерации промежуточных точек можно использовать алгоритм получения перестановки по номеру.
jknight
17.01.2017 10:11Вспоминается картинка про троллейбус из буханки хлеба :) Хотя, с чисто исследовательской позиции — достаточно интересно.
ShashkovS
17.01.2017 10:19+4А между тем движок хабра начал поддерживать LaTeX-нотацию для статей.
Для блочной формулы оборачиваем в $$display$$, для строчной — в $inline$.
$$display$$1966_{10} = 1\cdot10^3 + 9 \cdot 10^2 + 6 \cdot 10^1 + 6 \cdot10^0$$display$$
saluev
17.01.2017 10:55Кстати, подобная система счисления существует не только для весов разрядов 1!, 2!, 3! и так далее, но и для любых чисел: n1, n1·n2, n1·n2·n3, n1·n2·n3·n4, …
Danik-ik
17.01.2017 14:00О да, я этим пользовался, решая задачу по обфускации. Что-то типа такого:
Имя переменной должно начинаться с буквы, а дальше буквы, цифры и подчёркивания? Беру массив, где первые 26 (или 52 для case-sensitive, но тогда я этого не сообразил) — буквы, далее — десять цифр и подчёркивание. Беру номер переменной по порядку (они отсортированы по частоте употребления), и перевожу в систему счисления с основанием 26 в младшем разряде и 37 в следующих. По значению в разряде выбирается символ из массива, символы записываются от младшего разряда к старшему слева направо. Вуаля, идентификатор готов.
MrPhelko
17.01.2017 23:19-2Что-то тут не так, но мне кажется long имеет разрядность 64 и его максимальная величина 9223372036854775807, а из этого следует что 13! туда помещается. Вы наверно спутали с int.
mayorovp
18.01.2017 06:59+3В Си/С++ на наиболее распространенных компиляторах long имеет разрядность 32 бита.
master65
17.01.2017 23:19Возможно, факториальное разложение удобно при поиске перестановок с ограничениями (первый элемент может быть размещен на k позиций, второй – на l позиций, и так далее (k, l <= n)). Тут вопрос что более трудоемко — вычисление разложений или вычисление перманента матрицы смежности двудольного графа возможных перестановок.
ivanon1960
17.01.2017 23:24-2тут https://youtu.be/DbEHomTt_7Q
алгоритм перестановок с возможностью остановки и продолжения в любом месте
для перебора паролей самое то. скорость в 5 раз выше рекурсии
longclaps
Факториальное разложение числа —
бесполезныйвредный слой абстракции в тривиальной задаче перебора пермутаций.