Algoritmi Combinatori

8.1 Definizione degli algoritmi combinatori.

Gli algoritmi combinatori sono algoritmi progettati per risolvere problemi legati al conteggio, all'enumerazione e alla generazione di varie strutture combinatorie. Questi algoritmi sono utilizzati per lavorare con insiemi, sottoinsiemi, permutazioni, combinazioni e altri oggetti combinatori.

Tipi principali di problemi combinatori

• Permutazioni: Tutte le possibili combinazioni ordinate degli elementi di un insieme.
• Combinazioni: Tutti i possibili sottoinsiemi non ordinati di una dimensione data.
• Disposizioni: Tutti i possibili sottoinsiemi ordinati di una dimensione data.
• Partizioni: Tutti i possibili modi di dividere un insieme in sottoinsiemi.
• Oggetti combinatori: Altre strutture, come grafi, matrici ecc.

Vantaggi e svantaggi degli algoritmi combinatori

Vantaggi:

• Enumerazione completa: Questi algoritmi possono elencare tutte le possibili combinazioni, il che è utile per problemi di ricerca esaustiva.
• Flessibilità: Possono essere adattati per risolvere un'ampia gamma di problemi legati alla combinatoria.
• Intuitività: Molti algoritmi sono facili da capire e implementare grazie all'approccio ricorsivo e alla tecnica di backtracking.

Svantaggi:

• Esplosione combinatoria: Con l'aumentare della dimensione dell'input il tempo di esecuzione e l'uso della memoria possono aumentare drasticamente (per esempio, O(n!)).
• Non ottimalità: Nel caso di un gran numero di combinazioni questi algoritmi possono essere inefficienti e richiedere miglioramenti o sostituzioni con tecniche più avanzate (per esempio, l'uso della programmazione dinamica o algoritmi greedy).

Complessità temporale e spaziale degli algoritmi combinatori

Complessità temporale:

• Permutazioni: O(n!), dove n è il numero di elementi dell'insieme.
• Combinazioni: O(C(n, k)), dove C(n, k) è il coefficiente binomiale, uguale a n! / (k! * (n - k)!).
• Disposizioni: O(A(n, k)), dove A(n, k) è il numero di disposizioni, uguale a n! / (n - k)!.
• Sottoinsiemi: O(2^n), dato che ciascuno degli n elementi può essere incluso o meno nel sottoinsieme.

Complessità spaziale:

Generalmente O(n) per memorizzare risultati intermedi nel processo di costruzione ricorsiva, ma la memoria finale può essere richiesta per memorizzare tutti i risultati (per esempio, O(n * n!) per le permutazioni).

Esempi di algoritmi combinatori

8.2 Generazione di permutazioni.

Problema:

Trovare tutte le permutazioni uniche degli elementi di un insieme dato.

Algoritmo:

Si utilizzano metodi ricorsivi o iterativi per generare tutte le possibili combinazioni ordinate degli elementi.

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 Generazione di combinazioni

Problema:

Trovare tutte le combinazioni di una data dimensione di un insieme.

Algoritmo:

Si utilizzano ricorsione o iterazione per generare tutti i possibili sottoinsiemi di una dimensione data.

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 Generazione di partizioni di un insieme

Problema:

Trovare tutti i modi possibili per dividere un insieme in sottoinsiemi.

Algoritmo:

Si utilizza la ricorsione per generare tutte le possibili partizioni dell'insieme.

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

L'utilizzo di copy.deepcopy(part[:]) crea una copia profonda della lista part.. Questo significa che viene creato un nuovo elenco, indipendente, che non è collegato a quello originale part.. In questo modo, ogni elemento in result rappresenterà una partizione unica.