Algorytmy kombinatoryczne

8.1 Definicja algorytmów kombinatorycznych.

Algorytmy kombinatoryczne — to algorytmy, które służą do rozwiązywania zadań związanych z liczeniem, wymienianiem i generowaniem różnych struktur kombinatorycznych. Te algorytmy są stosowane do pracy z zbiorami, podzbiorami, permutacjami, kombinacjami i innymi obiektami kombinatorycznymi.

Główne typy zadań kombinatorycznych

• Permutacje: Wszystkie możliwe uporządkowane kombinacje elementów zbioru.
• Kombinacje: Wszystkie możliwe nieuporządkowane podzbiory o określonym rozmiarze.
• Układy: Wszystkie możliwe uporządkowane podzbiory o określonym rozmiarze.
• Podziały: Wszystkie możliwe sposoby podzielenia zbioru na podzbiory.
• Obiekty kombinatoryczne: Inne struktury, takie jak grafy, macierze itp.

Zalety i wady algorytmów kombinatorycznych

Zalety:

• Pełne wyliczenie: Te algorytmy mogą wymieniać wszystkie możliwe kombinacje, co jest przydatne w zadaniach przeszukiwania wyczerpującego.
• Elastyczność: Można je dostosować do rozwiązywania szerokiego zakresu zadań związanych z kombinatoryką.
• Intuicyjność: Wiele algorytmów jest łatwych do zrozumienia i implementacji dzięki podejściu rekursywnemu i technikom backtrackingu.

Wady:

• Eksplozja kombinatoryczna: Wraz ze wzrostem rozmiaru danych wejściowych czas wykonania i zużycie pamięci mogą gwałtownie rosnąć (na przykład, O(n!)).
• Nieoptymalność: W przypadku dużej liczby kombinacji te algorytmy mogą być nieefektywne i wymagać ulepszenia lub zastąpienia bardziej zaawansowanymi technikami (np. użycie programowania dynamicznego lub algorytmów zachłannych).

Złożoność czasowa i przestrzenna algorytmów kombinatorycznych

Złożoność czasowa:

• Permutacje: O(n!), gdzie n — liczba elementów zbioru.
• Kombinacje: O(C(n, k)), gdzie C(n, k) — współczynnik dwumianowy, równy n! / (k! * (n - k)!).
• Układy: O(A(n, k)), gdzie A(n, k) — liczba układów, równa n! / (n - k)!.
• Podzbiory: O(2^n), ponieważ każdy z n elementów może być włączony lub nie włączony do podzbioru.

Złożoność przestrzenna:

Zwykle O(n) do przechowywania wyników pośrednich w trakcie rekursywnego budowania, ale ostateczna pamięć może być wymagana do przechowywania wszystkich wyników (na przykład, O(n * n!) dla permutacji).

Przykłady algorytmów kombinatorycznych

8.2 Generowanie permutacji.

Zadanie:

Znajdź wszystkie unikalne permutacje elementów danego zbioru.

Algorytm:

Używana jest rekurencja lub metody iteracyjne do generacji wszystkich możliwych uporządkowanych kombinacji elementów.

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 Generowanie kombinacji

Zadanie:

Znajdź wszystkie kombinacje o zadanym rozmiarze z zbioru.

Algorytm:

Używana jest rekurencja lub iteracja do generacji wszystkich możliwych podzbiorów o zadanym rozmiarze.

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 Generowanie podziałów zbioru

Zadanie:

Znajdź wszystkie możliwe sposoby podzielenia zbioru na podzbiory.

Algorytm:

Używana jest rekurencja do generacji wszystkich możliwych podziałów zbioru.

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}))
        
        

Użycie copy.deepcopy(part[:]) tworzy głęboką kopię listy part.. Oznacza to, że tworzy nową, niezależną listę, która nie jest powiązana z oryginalnym part.. Dzięki temu każdy element w result będzie reprezentował unikalny podział.