Головна

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

  1. Алгоритм перебору всіх розбиттів множини.
  2. Алгоритми
  3. Алгоритми заповнення
  4. Алгоритми перебору розміщень
  5. Алгоритми перебору сполучень
  6. Алгоритми перебору та лексикографічний порядок

Алгоритм генерування перестановок множини А = {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. ▲



Алгоритми перебору розміщень | Алгоритми перебору сполучень

Основні правила комбінаторного аналізу. Поняття вибірки | Алгоритми перебору та лексикографічний порядок | Обчислення кількості розміщень і сполучень | Перестановки з повтореннями | Й спосіб. | Алгоритм перебору всіх розбиттів множини. | Біном Ньютона | Приклади виконання практичних завдань | Розв'язок. | Завдання до виконання |

© 2016-2022  um.co.ua - учбові матеріали та реферати