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

Як і в попередньому розділі, розглядатимемо перебір сполучень на множині A ={1,2,…, n }. Сполучення без повторень з n елементів по r — це r -елементна підмножина множини А. Позаяк порядок запису елементів множини неістотний, то для спрощення запису будемо сортувати елементи в сполученнях у висхідному порядку, і записувати їх як рядок чисел: наприклад, сполучення {4,1,3} будемо записуватимемо як 134.

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

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

Крок 1. Знаходимо позицію k першого справа числа, відмінного від n: .

Крок 2. Збільшуємо елемент на одиницю .

Елементи зліва залишаються без змін .

Елементи справа , де i > k стають рівними , .

Приклад 6.1. Нехай A = {1, 2, 3, 4}. Побудуємо 7 сполучень з повтореннями лексикографічно наступних після 1233. Наступне буде 1234, так як можливо збільшити останній елемент.

При пошуку наступного сполучення після 1234 бачимо, що збільшувати можна “3”. Отже отримаємо 124. Останній елемент теж повинен бути рівний “4”, бо не може бути менший за попередній. Отже отримуємо 1244.

Після нього буде 1333 - оскільки ми можемо збільшити тільки “2”, а інші елементи мають бути такими самими. Аналогічно знаходимо наступні елементи: 1334, 1344, 1444 та 2222.▲

Алгоритм побудови лексикографічно наступного сполучення без повторень за сполученням а₁а₂...а_r

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

Тоді максимальне значення, яке може набувати його останній елемент, рівне n. Максимум для передостаннього елементу рівний n-1, а не n. Доведемо це від зворотнього. Припустимо. що останній елемент рівний n, тоді наступний елемент має бути рівний n +1, але такого елементу немає в множині. Отже максимум передостаннього елементу n-1. Аналогічно можна довести, що максимум елементу на k -ій позиції рівний n-(r-k). Мінімум елементу – попереднє число сполучення, збільшене на одиницю.

Крок 1. Знайдемо перший справа елемент сполучення, який можна збільшувати. Він має бути менший за свій допустимий максимум, тобто .

Крок 2. Збільшимо елемент на одиницю b_k = а_k + 1.

Крок 3. Елементи зліва від не змінюємо b_i = а_i, i<k.

Крок 4. Елементи справа змінюємо на мінімальні, тобто такі, що на одиницю більші від попереднього:

b_i = b_i-1 + 1= а_k +i-k, i>k.

Приклад 6.2. Нехай А ={1, 2,3,4,5}. Знайдемо сполучення, наступне за {1,2,5,6} у лексикографічному порядку.

Це сполучення подамо рядком 1256. Маємо п = 6, r= 4. Перший справа з таких елементів, що а_i ≠ 6 – 4 + і, — це а ₂=2. Для обчислення наступного більшого сполучення збільшуємо а ₂ на 1 та одержуємо а ₂ = 3. Тепер нехай а₃ = 3+1=4 і a ₄ = 3 + 2 = 5. Отже, наступне в лексикографічному порядку сполучення — те, що зображене рядком 1345, тобто {1, 3, 4, 5}. ▲