16.01.2017 22:46
vkomen 17 6800 Источник
Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок 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!



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

Комментарии (17)


  1. longclaps
    17.01.2017 03:12
    #10016624
    +4

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


  1. mayorovp
    17.01.2017 08:55
    #10016826
    +7

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


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


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


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


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

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


    1. S_A
      17.01.2017 09:25
      #10016852
      +1

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

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


      1. ShashkovS
        17.01.2017 10:22
        #10016938
        +3

        Есть отличная книжка про такие штуки: А. Шень. Программирование: теоремы и задачи.


      1. nickolaym
        17.01.2017 13:24
        #10017358
        +3

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


        1. mayorovp
          17.01.2017 13:50
          #10017440
          +1

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


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


    1. vkomen
      17.01.2017 10:18
      #10016928

      Ответил не в ту ветку)


    1. vkomen
      17.01.2017 10:19
      #10016932

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


      1. mayorovp
        17.01.2017 10:25
        #10016942
        +1

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


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


  1. jknight
    17.01.2017 10:11
    #10016912

    Вспоминается картинка про троллейбус из буханки хлеба :) Хотя, с чисто исследовательской позиции — достаточно интересно.


  1. ShashkovS
    17.01.2017 10:19
    #10016930
    +4

    А между тем движок хабра начал поддерживать LaTeX-нотацию для статей.

    Для блочной формулы оборачиваем в $$display$$, для строчной — в $inline$.

    $$display$$1966_{10} = 1\cdot10^3 + 9 \cdot 10^2 + 6 \cdot 10^1 + 6 \cdot10^0$$display$$



  1. saluev
    17.01.2017 10:55
    #10016982

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


    1. Danik-ik
      17.01.2017 14:00
      #10017468

      О да, я этим пользовался, решая задачу по обфускации. Что-то типа такого:

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


  1. MrPhelko
    17.01.2017 23:19
    #10018698
    -2

    Что-то тут не так, но мне кажется long имеет разрядность 64 и его максимальная величина 9223372036854775807, а из этого следует что 13! туда помещается. Вы наверно спутали с int.


    1. mayorovp
      18.01.2017 06:59
      #10019068
      +3

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


  1. master65
    17.01.2017 23:19
    #10018700

    Возможно, факториальное разложение удобно при поиске перестановок с ограничениями (первый элемент может быть размещен на k позиций, второй – на l позиций, и так далее (k, l <= n)). Тут вопрос что более трудоемко — вычисление разложений или вычисление перманента матрицы смежности двудольного графа возможных перестановок.


  1. ivanon1960
    17.01.2017 23:24
    #10018706
    -2

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