Алгоритми перебору перестановок

Алгоритм генерування перестановок множини А = {1, 2,..., п } можна визначити як алгоритм побудови розміщень із n по n. Але для перестановок можна знайти простіший алгоритм.

Алгоритм побудови лексикографічно наступної перестановки за перестановкою а_1,а₂...а_n

Наведемо кроки алгоритму.

Крок 1. Знайти такі числа a_j і a_j+i, що (а_j < а_j+1,) (a_j+i a_j+2 ... а_п). Для цього треба знайти в перестановці першу справа пару сусідніх чисел, у якій число ліворуч менше від числа праворуч.

Крок 2. Записати в j -ту позицію таке найменше з чисел a_{j+ 1}, a_{j+ 2,}..., а_п, яке водночас більше, ніж a_j.

Крок 3. Записати у висхідному порядку число а_j і решту чисел a_{j+ 1,} a_j+2,...,a_n у позиції 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. ▲