Листок 15. Перестановки и сортировки (дополнительный)

"Нет дела более трудного по замыслу, более сомнительного по успеху, более оасного при осуществлении, чем вводить новые порядки"
Николо Макъявелли "Государь" (1513 г.)

0. Сколько перестановок у множества из n элементов?

Опр.1 Пусть множество P состоит из n элементов: p₁, p₂,..., p_n. Множеством Ключей К над множеством Р называется множество К, если:
а) взаимно-однозначное отображение К в Р и
б) на множестве К введено отношение порядка "меньше", т.е.

1. любые два элемента или равны между собой, или один меньше другого
2. если один элемент меньше другого и больше третьего, то другой больше третьего

(В математике множестао К называется линейно упорядоченным)

Опр.2 Сортировка - подстановка элементов нашего множества в порядке не убывания ключей.

Опр.2 Сортировка называется устойчивой, если элементы с равными ключами остаются на месте
Примечание 1. Далее, если не оговоренно, то сортировка устойчивая.

1. Доказать единственность подстановки, рашающую задачу сортировки

2. Пусть К и G - два различных множества ключей над Р. Введём "словарный порядок" на множестве пар (k_i,g_j):
(k_i,g_j) меньше (k_m,g_l) если k_i меньше k_m и если k_i = k_m, то g_j меньше g_l
ABC сначало отсотрировал по К ключам, а затем в группах с одинаковыми К-ключами по G - ключам, а Олег отсортировал, как указано выше.
а) получилось ли у них одно и тоже?
б) что будет в случае неустойчивой сортировки

3. Пусть на множестве К определено отношение порядка 1, а свойство 2 не выполняется
а) доказать, что и в этом случае возможна устойчивая сортировка
б) найти сортирующий алгоритм
в) единственен ли получаемый результат?

Инверсии

Опр. 4 Пусть в перестановке a₁,a₂,..., a_n: i<j, а a_i>a_j. Пара (a_i,a_j)называется инверсией

Опр. 5. Подпишем под перестановкой a₁,a₂,..., a_n числа, равные количестыу инверсий, которое образует элемент над ним в перестановке А. Получившаяся таблица называется таблицей инверсий.

4. Построить таблицу и найти все инверсии в перестановке (5, 9, 1, 8, 2, 6, 4, 7, 3)

5. Построить алгоритм построения таблицы инверсий по перестановке
б) наоборот

6. Насколько изменится число инверсий во всей перестановке, если поменять местами \ два соседних члена?
б) что вы можете сказать об изменении числа инверсий при других преобразованиях перестановки (т.е. при действии различных подстановок)

7. Рассмотрим две подстановки: в первой верхняя строчка 1, 2,.. n, а нижняя - произвольная перестановка, а другая обратна к первой, причем верхняя строчка тоже 1, 2,.. n. Доказать, что число инверсий в нижних строчках этих подстановок совпвдают.

8. Сколько существует перестановок n - порядока, имеющих k инверсий.

Перестановки мультимножества.

Опр.6. Мультимножество - это множество, для каждого элемента которого дополнительно указано количество копий этого элемента в мультимножестве.

9. Пусть М - мультимножество, содержащее n различных элементов a_k, причем для всех k число копий a_k равно m_k. Сколько существует перестановок такого мультимножества? (Перестановки различны, если их можно отличить)

Опр. 7. На множестве перестановок одного и того же множества введём операцию по следующему правилу (соединённое произведение)

1. Для двух перестановок взять соответсветсвующие им подстановки в смысле задачи № 7
2. Перемножить эти подстановки
3. Устойчиво отсортировать нижнюю строчку - это и есть произведение

10. Доказать, что перестановки множества образуют группу по этой операции.

11. Когда выполняется коммутативность?

12. Образуют ли перестановки мультимножества с этой операцией группу? Абелеву группу?

Опр. 8. Циклы в подстановках мультимножества определяются аналогично обычным циклам

13. Всегда ли (x₁,x₂,..., x_n) = (x₂,x₃,..., x_n,x₁)?

14. Любая перестановка мультимножества имеет единственное разложение в произведение независимых циклов.

Отрезки

Опр. 9. Элементы a_k,...,a_n образуют отрезок ⇐def⇒ a_k-1>a_k≤a_k+1 ≤...≤a_n>a_n+1

15. Найти все отрезки в перестановке (5 7 1 6 8 9 4 2 3)

16. Скольео перестановок множества (1, 2,..., n) содержит ровно k отрезков?

17. Говорят, что подстановка требует k чтений, если её надо просмотреть k раз слева направо, с тем что бы выписать все её элементы в неубывающем порядке
а) найти связь между отрезками и чтениями
б) докажите ваше предположение

Табло Янга и инволюции

Опр. 11 Запишем на нескольких первых строчках таблицы некоторое коллличество по-парно различных натуральных чисел. Если при этом:
1) Колличество элементов в строчке не меньше, чем во всех строчках её ниже
2) Каждый элемент меньше своего соседа справа и снизу и справа (если они есть)
- то таблица называется табло Янга (просто табло)

20. Найти все табло из элементов (1, 2, 3, 4)

21. Построить алгоритм:
а) определения места в табло нового элемента (введение)
б) Изменения табло после исключения заданного элемента
в) Посторения табло из заданных элементов.

22. Установить соответствие между упорядоченными парами табло одинаковой формы и подстановками.

23. Доказать, что если прямой подстановке соответсвует табло Р,0, то обратной 0,Р???????????

24. Найти связь между числом различных табло и инволюций данного множества.