Комбінаторні алгоритми

8.1 Визначення комбінаторних алгоритмів.

Комбінаторні алгоритми — це алгоритми, призначені для вирішення задач, пов'язаних з підрахунком, переліком та генерацією різних комбінаторних структур. Ці алгоритми застосовуються для роботи з множинами, підмножинами, перестановками, комбінаціями та іншими комбінаторними об'єктами.

Основні типи комбінаторних задач

• Перестановки: Усі можливі упорядковані комбінації елементів множини.
• Комбінації: Усі можливі неупорядковані підмножини заданого розміру.
• Розміщення: Усі можливі упорядковані підмножини заданого розміру.
• Розбиття: Усі можливі способи розбити множину на підмножини.
• Комбінаторні об'єкти: Інші структури, такі як графи, матриці тощо.

Переваги та недоліки комбінаторних алгоритмів

Переваги:

• Повний перелік: Ці алгоритми можуть перераховувати усі можливі комбінації, що є корисним для задач вичерпного пошуку.
• Гнучкість: Їх можна адаптувати для вирішення широкого спектру задач, пов'язаних з комбінаторикою.
• Інтуїтивність: Багатьом алгоритми легко зрозуміти і реалізувати завдяки рекурсивному підходу та техніці зворотнього відстеження (backtracking).

Недоліки:

• Комбінаторний вибух: Зі зростанням розміру вхідних даних час виконання і обсяг пам'яті можуть різко збільшуватися (наприклад, O(n!)).
• Неоптимальність: У випадку великої кількості комбінацій ці алгоритми можуть бути неефективними і вимагати покращення або заміни на більш просунуті техніки (наприклад, використання динамічного програмування або жадібних алгоритмів).

Часова та просторові складності комбінаторних алгоритмів

Часова складність:

• Перестановки: O(n!), де n — кількість елементів множини.
• Комбінації: O(C(n, k)), де C(n, k) — біноміальний коефіцієнт, рівний n! / (k! * (n - k)!).
• Розміщення: O(A(n, k)), де A(n, k) — кількість розміщень, рівна n! / (n - k)!.
• Підмножини: O(2^n), оскільки кожен з n елементів може бути включений або не включений у підмножину.

Просторова складність:

Зазвичай O(n) для зберігання проміжних результатів у процесі рекурсивного побудови, але підсумкова пам'ять може знадобитися для зберігання усіх результатів (наприклад, O(n * n!) для перестановок).

Приклади комбінаторних алгоритмів

8.2 Генерація перестановок.

Задача:

Знайти всі унікальні перестановки елементів заданої множини.

Алгоритм:

Використовується рекурсія або ітеративні методи для генерації усіх можливих упорядкованих комбінацій елементів.

Приклад коду на Python:

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
        
    backtrack(0)
    return result
        
print(permute([1, 2, 3]))

8.3 Генерація комбінацій

Задача:

Знайти всі комбінації заданого розміру з множини.

Алгоритм:

Використовується рекурсія або ітерація для генерації усіх можливих підмножин заданого розміру.

Приклад коду на Python:

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result
        
print(combine(4, 2))
        

8.4 Генерація розбиттів множини

Задача:

Знайти всі можливі способи розбити множину на підмножини.

Алгоритм:

Використовується рекурсія для генерації усіх можливих розбиттів множини.

Приклад коду на Python:

import copy
def partition_set(s):
    result = []

    def backtrack(part, rest):
        if not rest:
            result.append(copy.deepcopy(part[:]))
            return
        for i in range(len(part)):
            part[i].append(rest[0])
            backtrack(part, rest[1:])
            part[i].pop()
        part.append([rest[0]])
        backtrack(part, rest[1:])
        part.pop()

    backtrack([], list(s))
    return result

print(partition_set({1, 2, 3}))
        
        

Використання copy.deepcopy(part[:]) створює глибоку копію списку part. Це означає, що створюється новий, незалежний список, який не пов’язаний із вихідним part. Таким чином, кожен елемент у result буде представляти унікальне розбиття.