В этом посте я хочу показать вам метод создания отсортированных перестановок набора. Мы сосредоточимся на создании этих перестановок в лексикографическом или числовом порядке. Есть несколько способов сделать это, но некоторые из них лучше других с точки зрения эффективности.

Мы также рассмотрим способ получения перестановки в произвольной позиции в нашей лексикографически упорядоченной последовательности. С помощью этого метода мы можем напрямую генерировать искомую перестановку. Нам не нужно будет генерировать какие-либо из предыдущих перестановок в последовательности, которая предшествует нашей целевой.

Давайте начнем с того, что освежим нашу память о том, что такое перестановка.

Что такое перестановка?

Из комбинаторики перестановка, также называемая порядком, - это количество перестановок элементов в наборе. Количество перестановок в наборе из n элементов задается как n! (n факториал). Например, в наборе {1, 2, 3} есть 3! = 3x2x1 = 6 перестановок: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} и {3, 2, 1}.

Количество способов переупорядочить подмножество из k элементов из набора из n элементов определяется следующим образом:

Эта формула легко выводится из наших предыдущих определений. Давайте проиллюстрируем это на конкретном примере. Предположим, мы хотим найти количество способов расположить 4 книги из коллекции, состоящей из 10. Согласно нашей формуле, приведенной выше, мы имеем:

Мы можем думать об этом следующим образом. В числителе указано количество способов расположить 10 книг - это 10!. Но нас интересуют только первые 4 способа. Итак, оставшиеся 6 способов делим - или (10-4)! = 6!:

Наконец, имейте в виду, что при перестановке мы считаем все возможные порядки в наборе.

Генерация перестановок

Мы можем генерировать перестановки разными методами. И, в зависимости от выбранного нами метода, порядок результирующих перестановок будет меняться. Кроме того, некоторые методы будут более эффективными, чем другие. Роберт Седжвик в своей обзорной статье Методы генерации перестановок заключил, что самый быстрый алгоритм для генерации перестановок - это алгоритм Heap. Однако результирующие перестановки этого метода не находятся в лексикографическом порядке.

Перестановки в лексикографическом порядке

В нашем случае мы хотим перечислить их в лексикографическом или числовом порядке. В качестве примера сгенерируем перестановки набора {0 1 2}. Мы берем наименьшее число, 0, и помещаем его впереди, затем добавляем оставшиеся 1 и 2. Это дает нам первую перестановку {0 1 2}. Затем, оставив 0 впереди, мы меняем местами 1 и 2: {0 2 1}. Мы повторяем процесс, но теперь с 1 впереди. Итак, получаем перестановки {1 0 2} и {1 2 0}. Наконец, повторяем с 2 спереди: {2 0 1} и {2 1 0}. Получающийся список перестановок следующий.

1. {0 1 2} 
2. {0 2 1} 
3. {1 0 2} 
4. {1 2 0} 
5. {2 0 1} 
6. {2 1 0}

Обратите внимание, что список упорядочен по номерам. Другими словами, каждое последующее расположение чисел больше предыдущего.

В этом примере у нас было всего 6 перестановок набора {1 2 3}. Так что перечислить их все было несложно. Однако по мере того, как размер набора начинает расти, количество перестановок увеличивается еще быстрее. Помните, что он следует факториальной скорости роста - количеству перестановок набора размером n = n!. Итак, если мы хотим сгенерировать перестановки набора {0 1 2 3 4 5 6 7 8 9}, мы получим 10! = 3 628 800 перестановок набора.

Классический алгоритм генерации перестановок в лексикографическом порядке выглядит следующим образом. Рассмотрим список чисел s = [1, 2, 3, 4]. Обратите внимание, что последовательность изначально отсортирована. Этого требует алгоритм. Теперь, предполагая, что индексирование списка начинается с нуля, мы действуем следующим образом:

шаг 1) Найдите наибольший индекс i такой, что s [i] ‹s [i + 1]. Если мы не можем найти такой индекс, это означает, что мы находимся на последней перестановке последовательности:

В нашем списке i = 2, поскольку число в индексе 2, s [2] = 3 меньше числа в индексе i + 1 = 3 , s [3] = 4 и i = 2 - наибольший индекс, удовлетворяющий этому условию.

шаг 2) Найдите наибольший индекс j, который больше i, такой, что s [i] ‹s [j] :

Глядя на наш список, мы получаем j = 3. Это удовлетворяет нашему условию (s [2] = 3) ‹(s [3] = 4)

шаг 3) замените значение s [i] на значение s [j]:

Итак, мы меняем местами значения двух индексов. Наш список выглядит следующим образом: s = [1, 2, 4, 3]

шаг 4) Поменяйте последовательность от s [i + 1] до последнего элемента включительно:

В нашем случае i = 2. Итак, следующий индекс i + 1 = 3, который является последним индексом нашего списка, поэтому он остается прежним. Наша следующая перестановка - s = [1, 2, 4, 3].

Мы продолжаем этот процесс со следующими перестановками, пока не будет выполнено условие s [i] ‹s [i + 1]. Это будет указывать на то, что мы достигли последней перестановки последовательности.

Нахождение N-й перестановки в упорядоченной последовательности

Вышеупомянутый метод генерирует все перестановки набора элементов по порядку. Этот порядок всегда лексикографический. Но что, если мы захотим найти лексикографически упорядоченную перестановку в произвольной позиции в последовательности? Например, если мы хотим найти 980 000 перестановку в наборе {0 1 2 3 4 5 6 7 8 9}? Как мы упоминали выше, мы знаем, что в этой последовательности есть 3 628 800 перестановок. Используя наш предыдущий алгоритм, мы должны были бы сгенерировать все предыдущие 979 999 перестановок, прежде чем перейти к 980 000.

Для этой задачи мы могли бы использовать факториальную систему счисления, чтобы помочь нам найти нашу произвольную перестановку более эффективно.

Факториальная система счисления

Факториальная система счисления или factoradic - это система счисления смешанный основание. Это означает, что основание или основание каждой цифры изменяется вместе с ее положением. Напротив, наши более знакомые системы счисления, такие как десятичная или двоичная, сохраняют фиксированное основание для всех цифр в каждой позиции.

В следующей таблице показана факториальная система счисления.

Чтобы преобразовать значение из десятичного в факторадикальное, нам просто нужно взять целочисленное деление значения по основанию системы счисления, начиная с 1, 2, 3, ... Во время последовательных делений мы отслеживаем остатки - до тех пор, пока деление не приведет к 0. Остаток от каждого деления будет соответствовать фактической цифре числа в этой позиции, идущей справа налево. Например, чтобы преобразовать 256 (десятичное) в представление факториального числа:

256 / 1 = 256, remainder 0 
256 / 2 = 128, remainder 0 
128 / 3 =  42, remainder 2 
 42 / 4 =  10, remainder 2 
 10 / 5 =   2, remainder 0 
  2 / 6 =   0, remainder 2

Расставляя остатки, начиная снизу и вверх, получаем фактическое число: 202200. В качестве упражнения вы можете попытаться преобразовать его обратно в десятичное представление, используя приведенную выше таблицу. Нам просто нужно умножить цифру в каждой позиции на соответствующее разрядное значение, а затем сложить их все.

Использование факторной системы счисления для нахождения N-й перестановки

Теперь мы готовы использовать факториальную систему счисления, чтобы помочь нам найти нашу произвольную перестановку в последовательности. Оказывается, существует связь между этой системой счисления и лексикографически упорядоченными перестановками множества. Это соотношение или отображение известно как код Лемера.

Теперь давайте вернемся к нашему вопросу о нахождении 980 000 перестановки в лексикографически упорядоченных перестановках множества {0 1 2 3 4 5 6 7 8 9}. Как видите, набор изначально отсортирован (в порядке неубывания). Это самая низкая перестановка в наборе. Помните, что с помощью этого метода нам не нужно генерировать все предыдущие перестановки, чтобы перейти к той, которую мы ищем.

Действуем следующим образом. Во-первых, мы собираемся присвоить индекс - начиная с 0– всем цифрам в наборе. Первоначально индекс 0 соответствует цифре 0, индекс 1 - цифре 1 и так далее, вплоть до индекса 9, соответствующий цифре 9. Кроме того, мы перечислим каждую перестановку в последовательности, начиная с 0. Итак, первоначальный порядок набора - номер перестановки 0. Следовательно, теперь нам нужно найти перестановку (980,000-1) = 979,999.

Теперь берем число 979,999 и начинаем с деления его на (n -1)!, где n - количество элементов в наборе. -в нашем случае n = 10–, поэтому мы начинаем деление на 9!. Мы будем отслеживать остаток и целое частное:

Initial set: {0 1 2 3 4 5 6 7 8 9} 
979,999 / 9! = 2, remainder 254,239 
permutation 1st digit: 2

Здесь результат целочисленного деления, 2, указывает индекс внутри нашего набора числа, который соответствует первой цифре в нашей 979 999-й перестановке. Индекс 2 соответствует номеру 2. Теперь мы вынимаем это число из набора, берем остаток в качестве нового числителя и переходим к следующей итерации, вычитая 1 из n в знаменателе ( п-1)!. Мы продолжим этот процесс до тех пор, пока не будет (n -1) включительно! = 0!:

set: {0 1 3 4 5 6 7 8 9} 
254,239 / 8! = 6, remainder 12,319 
permutation 2nd digit: 7 
set: {0 1 3 4 5 6 8 9} 
12,319 / 7! = 2, remainder 2,239 
permutation 3rd digit: 3 
set: {0 1 4 5 6 8 9} 
2,239 / 6! = 3, remainder 79 
permutation 4th digit: 5 
set: {0 1 4 6 8 9} 
79 / 5! = 0, remainder 79 
permutation 5th digit: 0 
set: {1 4 6 8 9} 
79 / 4! = 3, remainder 7 
permutation 6th digit: 8 
set: {1 4 6 9} 
7 / 3! = 1, remainder 1 
permutation 7th digit: 4 
set: {1 6 9} 
1 / 2! = 0, remainder 1 
permutation 8th digit: 1 
set: {6 9} 
1 / 1! = 1, remainder 0 
permutation 9th digit: 9 
set: {6} 
0 / 0! = 0, remainder 0 
permutation 10th digit: 6

Складывая все цифры вместе, получаем: {2 7 3 5 0 8 4 1 9 6}. Это 980 000 перестановка в лексикографическом порядке нашего набора.

Обратите внимание, что результат каждого целочисленного деления выше соответствует каждой цифре в десятичном представлении 979,999. Если сложить эти цифры вместе, получим 2623031010. Это факториальное представление десятичного числа 979,999:

979,000(decimal) = 2623031010(factoradic)

Это иллюстрирует соответствие между факторной системой счисления и лексикографическими перестановками. Точно так же мы могли бы начать с преобразования 979 000– в соответствии с процедурой, описанной в предыдущем разделе, в его факториальное числовое представление. Затем используйте каждую цифру в фактурном числе в качестве индекса для нашего сужающегося набора, как мы делали выше.

Приложения перестановок

В этой статье мы перешли от основных определений перестановки к обсуждению различных способов их генерации. Нас особенно интересовало создание перестановок в лексикографическом порядке и то, как мы можем сделать это эффективно. В заключение я кратко упомяну некоторые применения перестановок в различных областях.

Некоторые из этих приложений включают алгоритмы обнаружения и исправления ошибок в теории информации. Перестановки используются для анализа алгоритмов сортировки в информатике. Они также используются для описания последовательностей РНК в биологии. И они появляются во многих разделах математики.

Надеюсь, это обсуждение перестановок дало вам другую перспективу и вдохновило вас продолжить изучение предмета.

Первоначально опубликовано на https://stemhash.com 31 августа 2020 г.