Как перебрать все перестановки и о факториальном разложении натуральных чисел

    Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок n предметов равно попросту факториалу числа n

    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!



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

    Подробнее
    Реклама
    Комментарии 17
    • +4
      Факториальное разложение числа — бесполезный вредный слой абстракции в тривиальной задаче перебора пермутаций.
      • +7

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


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


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


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


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

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

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

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

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


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

            • 0
              Ответил не в ту ветку)
              • 0
                А как распараллелить?
                • +1

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


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

              • 0
                Вспоминается картинка про троллейбус из буханки хлеба :) Хотя, с чисто исследовательской позиции — достаточно интересно.
                • +4
                  А между тем движок хабра начал поддерживать LaTeX-нотацию для статей.

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


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

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

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

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

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.