Часть 0. Понятие перестановки. Разложение на циклы.

[Все темы по перестановкам]

Теория:
1) Липский. Комбинаторика для программистов. 1988 (п.1.3)
2) Окулов. Программирование в алгоритмах. 2004
3) Кнут. Том 4. Выпуск 2. Генерация всех картежей и перестановок. 2008
Видео:

Практика:

Задача: [Обратная перестановка]
Сама задача несложная. Нужно понять принцип суперпозиции двух перестановок, откуда вытекает понятие обратной перестановки. Все справочные материалы можно найти в Липском.
[Решение]

Задача:[Степень перестановки]
Рассмотрим перестановку: (5 7 8 2 3 1 4 6)
Как известно любую перестановку можно разложить ни циклы. Данная перестановка выглядит вот так:

Теперь давайте рассмотрим маленький цикл [274].
Как видно для того, чтобы номера вершин “встали на свои позиции” нужно получить третью степень исходной перестановки.

Проделаем тоже самое для большого цикла [15386]. Здесь нам придется получить пятую степень перестановки.
Вопрос: Когда все 7 позиций “встанут” на свои места. Очевидно, когда первый цикл сделает 5 оборотов, а второй – 3. Следовательно нужно получить 15-ую степень исходной перестановки.

В общем случае нужно найти НОК(lcm) длин всех циклов, которые присутствуют в перестановке.
[Решение]

Задача: [Восстановление перестановки]
Интересный факт: в разной литературе дают разное определение таблице инверсий перестановки.
В задаче: Phi[i]    = amount(j): П(j) > П[i], j<i
Окулов:   Phi[П[i]] = amount(j): П[j] < П[i], j>i
Кнут:     Phi[П[i]] = amount(j): П[j] < П[i], j<i

Сути дела это правда не меняет. Главное быть в курсе по какому правилу получается эта таблица инверсий.

Что касается задачи. Будем последовательно находить положение элементов в перестановке на основе данной таблице инверсий. При этом заполнять перестановку будем элементами в порядке возрастания. Более подробно об этом процессе читайте у Окулова.
[Решение]