Головна |
Алгоритм генерування перестановок множини А = {1, 2, ..., п} можна визначити як алгоритм побудови розміщень із n по n. Але для перестановок можна знайти простіший алгоритм.
Алгоритм побудови лексикографічно наступної перестановки за перестановкою а1,а2...аn
Наведемо кроки алгоритму.
Крок 1. Знайти такі числа aj і aj+i, що (аj<аj+1, ) (aj+i aj+2 ... ап). Для цього треба знайти в перестановці першу справа пару сусідніх чисел, у якій число ліворуч менше від числа праворуч.
Крок 2. Записати в j-ту позицію таке найменше з чисел aj+1, aj+2,..., ап, яке водночас більше, ніж aj.
Крок 3. Записати у висхідному порядку число аj і решту чисел aj+1, aj+2,...,an у позиції j + 1,..., п.
Приклад 5.1.Побудуємо 2 перестановки, наступні в лексикографічному порядку за 34521. Згідно першого кроку j=2, бо 4<5>2>1. Отже, перше число (3) залишається на місці, а збільшується друге число(4). Розглянемо послідовність чисел 521. Серед них найменше число, більше від 4, це 5. Тепер на другому місці 5, а решту чисел розміщуємо у вихідному порядку: 35124.
Побудуємо наступну перестановку після 35124. Згідно першого кроку j =4, і щоби отримати наступну перестановку, треба збільшити "2", поставивши замість нього "4", так як справа немає іншого числа більше "2". Переставивши місцями два останніх числа, ми отримаємо 35142.▲
Іншим алгоритмом для перебору всіх розміщень є генерування усіх сполучень (див. наступний розділ), після чого з кожного сполучення генерувати всі можливі перестановки.
Зауважимо також, що для перебору перестановок з повтореннями чи без повторень алгоритм не відрізнятиметься. Єдина відмінність полягатиме у тому, що для перестановок без повторень рівності у кроці 1 будуть строгими.
Приклад 5.2. Побудуємо 5 перестановок, наступних в лексикографічному порядку за 324122311. Знаходимо перші 2 числа справа, перше х яких менше другого: . Отже, на місце першого числа ставимо "3", а решту ставимо в порядку зростання (112), отримуємо 3241243112. Наступне число отримується перестановкою двох останніх чисел 3241243121. Легко побачити, що наступне 3241243211.
Щоб знайти наступне після 3241243211, знову знаходимо перші 2 числа справа, перше х яких менше другого: .
Збільшуємо "2" на наступне число, наявне справа від нього у перестановці - "3". Решту чисел сортуємо по зростанню: 3241311224. ▲
Основні правила комбінаторного аналізу. Поняття вибірки | Алгоритми перебору та лексикографічний порядок | Обчислення кількості розміщень і сполучень | Перестановки з повтореннями | Й спосіб. | Алгоритм перебору всіх розбиттів множини. | Біном Ньютона | Приклади виконання практичних завдань | Розв'язок. | Завдання до виконання |