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

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

Алгоритм подібний до звичайного визначення наступного числа.

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

Крок 2. Збільшуємо елемент на одиницю. Елементи , де i < k залишаються без змін. Елементи , де i > k стають рівними одиниці.

Приклад 4.1. Нехай A = {1, 2,3}. Побудуємо 6 розміщень з повтореннями лексикографічно наступних після 1222. Наступне буде 1223, так як можливо збільшити останній елемент. Після нього буде 1231 - оскільки 4-й елемент ми збільшити не можемо, то збільшуємо 3-й, а 4-й ставимо рівним одиниці. Як бачимо, маємо аналогію з переносом розряду, подібно до десяткового числення. Наступні елементи, відповідно будуть 1232,1233, 1311 та 1312.▲

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

Алгоритм від попереднього відрізняється тим, що у розміщеннях не може бути повторів, і тому потрібно “оновлювати” елементи розміщення, не порушуючи цієї властивості.

Крок 1. Знайдемо множину B “вільних” чисел, яких немає у розміщенні B = A \

Крок 2. Шукаємо перший справа елемент у розміщенні, який можна збільшити. Якщо у B є елементи, які більші за а_r, то вибираємо серед них такий, що:

.

Якщо у B немає елементів, більших за а_r, то додаємо до B елемент а_r, і шукаємо:

.

Якщо у B немає елементів, більших за а_r-1, то додаємо до B елемент а_r-1, і т.д. Продовжуємо цей процес, поки не знайдемо:

,

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

Крок 3. Обчислюємо наступне розміщення. Записати в k-ту позицію розміщення знайдене число і вилучити його з множини B. Записати у висхідному порядку число - найменші з чисел у множині B, розмістивши їх на позиціях k + 1, k + 2,..., r.

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

Обчислимо наступне розміщення після 124. Оскільки 3-й елемент ми збільшити не можемо, то збільшуємо 2-й елемент, тобто заміняємо “2” на “3”. На останньому місці не можна ставити одиницю, бо вона вже є у розміщенні, і ставимо найменший елемент, такий що його немає в розміщенні, тобто “2”. Отже отримуємо 132.

Наступне розміщення після 132 рівне 134, тому що можливо збільшити останній елемент. Яке розміщення буде після 134? Останній елемент ми не можемо збільшити, але можемо збільшити передостанній. Тому наступне розміщення 142.▲