Теперь, когда знаем, как найти перестановку от порядкового номера, как можно найти порядковый номер от перестановки?
Сначала, нужно знать перестановку.
Затем, вычисляем комбинационное число. (Как только получим комбинационное число, можем найти порядковый номер).
ПОРЯДКОВЫЙ НОМЕР
↑
КОМБИНАЦИОННОЕ ЧИСЛО
↑
ПЕРЕСТАНОВКА
Это - обратный путь нахождения перестановки из порядкового номера.
Каков порядковый номер для:
B C А D F E?
Если первая комбинация:
А B C D E F
Шаг 1
(§ 3)
Теперь, когда знаем перестановку и начальную перестановку, найдем комбинационное число заданной перестановки.
Чтобы вычислить комбинационное число, взглянем как перестановка и начальная комбинация отличаются:
5 4 3 2 1 0
B C A D F E
А B C D E F
Сначала, нужно взглянуть на элемент в 5-й позиции (мы видим, что это B) и узнать, где он находится в начальной перестановке. Элемент B в начальной перестановке находится в 4-й позиции. Значит, сделаем сдвиг 1 элемент. Так что его комбинационное число равно 1.
А C D E F
B _ _ _ _ _ (1)
Затем, взглянем на элемент в 4-й позиции (это C) и узнаем, где он находится в начальной перестановке (Ранее использованный элемент B не учитываем). Как видите, сделан сдвиг на 1 элемент, так что его комбинационное число равно 1.
А D E F
B C (1) (1)
Затем, взглянем на элемент 3 в позиции (это A) и узнаем, где он находится в начальной перестановке. Посмотрим, на каком месте он находится в начальной перестановке. Видно, на первом месте. Он не пропускал никаких элементов, таким образом его комбинационное число равно 0.
D E F
B C А _ _ _ (1) (1) (0)
Теперь, посмотрим на элемент в позиции 2 (это D) и узнаем, где он находится в начальной перестановке. Видно, что это D, теперь взглянем, какой сдвиг надо сделать в начальной перестановке, чтобы найти его. Так как он стоит на первом месте, то не надо делать сдвигов, поэтому его комбинационное число равно 0.
E F
B C А D _ _ (1) (1) (0) (0)
Затем, нужно посмотреть на элемент в позиции 1 (это E) и узнать, где он находится в начальной перестановке. Как видим, в начальной перестановке надо сделать один сдвиг, поэтому комбинационное число равно 1.
E
B C А D F _ (1) (1) (0) (0) (1)
Теперь, остался только один выбор. Вставим E в позицию 0 без сдвига.
B C А D F E (1) (1) (0) (0) (1) (0)
Шаг 2
(§ 3)
Теперь, когда у нас есть комбинационное число, можно найти порядковый номер.
Что бы найти порядковый номер:
Умножим комбинационное число на количество изменений каждого элемента.
1 1 0 0 1 0
120 24 6 2 1 1
Он должен выглядеть так:
=1×120 + 1×24 + 0×6 + 0×2 +1×1 + 0×1
= 145
Это число - порядковый номер
Актуальность
Приведенный нами алгоритм может использоваться в различных компьютерных программах для ускорения поиска. Для нахождения перестановки по заданному номеру,
или же номера заданной перестановки в лексикографическом упорядочении требует перечисления всех перестановок с предыдущими номерами, что требует в среднем времени порядка n!/2
Наш алгоритм использует время порядка n. Например: Если n= 1000, то обычный метод требует времени порядка 1000!
Этот алгоритм может быть использован в различных компьютерных программах использующих поиск перестановок или их порядка, что часто встречается в различных программах. Например: игры, шахматы и т.д.
Например:
Есть 6 полок
S1 S2 S3 S4 S5 S6
Есть 6 книг
B1 B2 B3 B4 B5 B6
Есть ограничение: B1 не может войти в S1 или S2.
Что было бы первой рабочей комбинацией?
Если вы дадите эту задачу компьютеру, он использует "грубую силу"(Brute force), чтобы решить это. (что означает, подставлять каждую комбинацию одну за другой).
Это заняло бы много времени. И выглядело бы так:
B1 B2 B3 B4 B5 B6
B1 B2 B3 B4 B6 B5
………
И, так продолжалось бы дальше.
Но, при использовании рассмотренного метода данной работы, компьютер может найти первую комбинацию очень легко и быстро.
Так как мы знаем, что B1 не будет изменяться 120 шагов, можно заставить компьютер пропускать все их. Тогда это выглядело бы так:
B2 B1 B3 B4 B5 B6
Если бы компьютер искал, используя грубую силу, он рассматривал бы все комбинации до того, как он получил бы правильный ответ. С новым методом можно вынудить компьютер пропускать 24 шага, и он найдет ответ: 144. (который имеет комбинационное число 1-1-0-0-0-0 и перестановку B2-B3-B1-B4-B5-B6).
При использовании этого метода, можно было бы сэкономить много времени на компьютерные проблемы как эта.
Прикладное применение
Из предидущих глав мы получили алгоритм вычиляющий порядок перестановок. В этой главе мы покажем поверхностное применение этого алгоритма для поиска информации различного рода. Попытаемся создать систему поиска используя перестановку как слово,а порядковый номер как индекс.
Итак, мы можем определить на каком порядке находится перестановка определенных знаков (чисел, буков, символов), другими словами мы можем найти индекс перестановки. Значит если задать ключевую перестановку, тоесть слово или сочетание слов и знаков (пробел примим в виде знака), то при сортировке по алфавитному порядку можно найти его порядковый номер. А затем и само расположение этого слова, используя несколько вспомогательных программ.
Пример 1
Пусть у нас есть множество слов S={apple,burger,cotton, …, knife,...,York,zero}
(слова подобраны в алфавитном порядке) состоящее из 26 слов. И нам нужно найти слово cotton и knife которые имеют номера 3 и 11 в этом множестве. Это легко так как каждое слово стоит в порялке порядке.
Усложним задачу, добавим во множество по несколько слов для каждой буквы.
S={apple, animal, area, …, burger, bread, …,zoo, zero}
Теперь слов больше и они не расположены в порядке. Чтобы найти какое-нибудь слово придется пропускать другое варианты, иначе это займет много времени.
Для этого и будем использовать наш алгоритм.
Найдем расположение слова knife.
У нас всего 27! комбинаций. (0 – пробел)
a b c d … z 0
a b c d … 0 z
27!
… … …
0 z y x … b a
Так как в слове knife всего 5 буков, то множество нужных нам комбинаций выглят так
k n i f e 0 a b … z
K n i f e 0 a b... y
21!
.........
k n i f e 0 z y … a
Заключение
Нами найден алгоритм нахождения перестановки по её порядковому номеру в лексикографическом упорядочении и порядкового номера заданной перестановки.
Алгоритм затрачивает на поиск порядка n т.е. является линейным, в то время как обычные методы для решения этой же задачи экспоненциальные. Тоесть имеют порядок Сn, где n – порядок перестановки, а С – постоянное число большее 1.
Этот алгоритм может быть использован с различными модификациями в различных компьютерных программах поиска, где используются перестановки.
Литература
Богомолни Александр, Перестановки
https://www.cut-the-knot.org/do_you_know/permutations.shtml
Вычисление Перестановок и Вопросов о Собеседовании при приеме на работу, Вычисления
Перестановки, https://www.bearcave.com/random_hacks/permute.html
Коннел E.H., Элементы Абстрактной и Линейной Алгебры,
https://www.math.miami, edu/ec/book/author.html
Джонс Филип. Перестановки и комбинации, Мир Заказывает Энциклопедию,
Математика, доктор, Перестановки и Комбинации, Математический Forum@Drexel,
Математика Forum@1994-2005.
Перестановки и Комбинации, Математическая Страница, 2003-2005, Лоренс Спектор.
Доктор E. Шакшуки, Объяснение Алгоритма, март 2005