Розділ 4. Алгоритми перестановок та сортування.

4.1. Перестановка

Перестановкою скінченної множини називають деяке розташування його елементів у ряд. Дуже багато задач зводяться до складання перестановок. Ми вже згадували про підалгоритм побудови перестановок для розв'язання задачі про комівояжера. Розглянемо ще декілька задач, що приводять до побудови перестановок.

Задача про чергу у приймальній.

В приймальній зібралося п відвідувачів. Попереднє опитування дозволило з'ясувати, скільки часу повинен виділити директор кожному відвідувачу (ti). Треба так організувати прийом, щоб відвідувачі знаходилося у приймальній настільки можливо менше часу.

Розв'язком цієї задачі буде деяка перестановка чисел

,

яка відповідає черзі прийому відвідувачів.

Позначимо через ( )час чекання у приймальні відвідувача i за тією чергою, яка задає перестановка . Очевидно, що

( )= ( )+t

( )=0;

В цьому випадку формулюємо таке: знайти таку перестановку , на якій величина

F( ) =

приймає найменше значення.

Задача про приймальну - найпростіша з задач складання черг. Ця задача потребує складання розкладу, вона зводиться до суворого впорядкування виконання деяких робіт. Після відповідної формалізації така задача зводиться до пошуку екстремальної перестановки. Функцію екстремуму називають оптимізуючою функцією або функцією-крітерієм.

Ще один приклад такої задачі: задача про наречених.

В

Сережа

Оля

Зоя

Саша

Лиля

Андрей

деякому царстві на одинокому острові живуть n хлопців та m дівчат. Треба їх найкращим чином переженити. Але: Оля любит Сашу, и Зоя любит Сашу, а Саша любит Лилю, Лиля же любит Андрея, да Андрей никого не любит, но зато вот Саша по-прежнему любит Олю...

Вважається, що не виключено можливість будь-якого шлюбу, але деякі шлюби мають переваги перед іншими: оцінка шлюбу задається значенням a , які визначаються експертним шляхом.

Ця задача відноситься до класу задач про призначення.

Переглянуті задачі зводяться до побудови перестановок. Розглянемо алгоритми їх побудови.

Алгоритм 1.

Розглянемо деяку перестановку з натуральних чисел 13 5 4 2

Знайдемо першу з кінця перестановки впорядковану пару (3 5). Перше число називають числом, що обриває. Хвіст перестановки утворює послідовність чисел, яка починається з числа, що обриває.

Підалгоритм ревпорядкування хвоста перестановки.

1. замінити число, що обриває, на найменше з хвоста перестановки, яке більше його.

2. всі інші числа з хвоста перестановки разом з тим, що обриває розташивати в порядку зростання:

1 3 5 4 2 число, яке обриває - 3.

3 5 4 2 хвіст перестановки

Робота буде закінчена, коли всі числа будуть розташовані в порядку спадання.

Таблиця 4.1. Таблиця трасування створення перестановок

№ перестановки	перестановк а	число, що обриває	хвіст перестановки	ревпорядкува ння хвоста перестановки
1	1 2 3 4	3	3 4	4 3
2	1 2 4 3	2	2 4 3	3 2 4
3	1 3 2 4	2	2 4	4 2
4	1 3 4 2	3	3 4 2	4 2 3
5	1 4 2 3	2	2 3	3 2
6	1 4 3 2	1	1 4 3 2	2 1 3 4
7	2 1 3 4	3	3 4	4 3
8	2 1 4 3	1	1 4 3	3 1 4
9	2 3 1 4	1	1 4	4 1
10	2 3 4 1	3	3 4 1	4 1 3
11	2 4 1 3	1	1 3	3 1
12	2 4 3 1	2	2 4 3 1	3 1 2 4
13	3 1 2 4	2	2 4	4 2
14	3 1 42	1	1 4 2	2 1 4
15	3 2 1 4	1	1 4	4 1
16	3 2 4 1	2	2 4 1	4 1 2
17	3 4 1 2	1	1 2	2 1
18	3 4 2 1	3	3 4 2 1	4 1 2 3
19	4 1 2 3	2	2 3	3 2
20	4 1 3 2	1	1 3 2	2 1 3
21	4 2 1 3	1	1 3	3 1
22	4 2 3 1	2	2 3 1	3 1 2
23	4 3 1 2	1	1 2	2 1
24	4 3 2 1	2	2 3	3 2

Таким чином маємо 4!=24 перестановки.

Алгоритм 1 зобразимо так:

перевпорядкувати

хвіст перестановки

рис. 4.1. Блок-схема алгоритму 1 побудови перестановок.

Для цього алгоритму треба використати підалгоритм впорядкування деякого буферного масиву, який ми називаємо хвостом перестановки.

Для розгляду другого алгоритму побудови перестановок використаємо

таке поняття, як обертання - це процес, в якому перше число стає на останнє місце.

Таблиця 4.2 Трасування створення перестановок за допомогою алгоритму 2.

№ перестановки	перестановка
1	1 2 3 4	m=4:<1 2 3 4>	2 3 4 1
2	2 3 4 1	m=4:<2 3 4 1>	3 4 1 2
3	3 4 1 2	m=4:<3 4 1 2>	4 1 2 3
4	4 1 2 3	m=4:<4 1 2 3> m=3:<l 2 3>	1 2 3 4 (Im=m) 3 1 2 4
5	3 1 2 4	m=3:<3 1 2>	2 3 1 4
6	2 3 1 4	m=3:<2 3 1> m=2: <1 2>	1 2 3 4 (Im=m) 2 1 3 4

Перестановки дуже важливі для вивчення алгоритмів сортування, тому що вони слугують для подання невпорядкованих вхідних даних. Для аналізу ефективності різноманітних методів сортування треба підраховувати кількість перестановок, які треба повторювати деякий крок алгоритму визначену кількість раз.