Algoritmos Combinatórios

8.1 Definição de algoritmos combinatórios.

Algoritmos Combinatórios são algoritmos destinados a resolver problemas relacionados à contagem, enumeração e geração de várias estruturas combinatórias. Esses algoritmos são aplicados para trabalhar com conjuntos, subconjuntos, permutações, combinações e outros objetos combinatórios.

Principais tipos de problemas combinatórios

• Permutações: Todas as combinações ordenadas possíveis dos elementos de um conjunto.
• Combinações: Todos os subconjuntos não ordenados possíveis de tamanho especificado.
• Arranjos: Todos os subconjuntos ordenados possíveis de tamanho especificado.
• Partições: Todas as maneiras possíveis de dividir um conjunto em subconjuntos.
• Objetos combinatórios: Outras estruturas como grafos, matrizes etc.

Vantagens e desvantagens dos algoritmos combinatórios

Vantagens:

• Enumeração completa: Esses algoritmos podem enumerar todas as combinações possíveis, o que é útil para problemas de busca exaustiva.
• Flexibilidade: Podem ser adaptados para resolver uma ampla gama de problemas relacionados à combinatória.
• Intuitividade: Muitos algoritmos são fáceis de entender e implementar devido à abordagem recursiva e à técnica de backtracking.

Desvantagens:

• Explosão combinatória: Com o aumento do tamanho dos dados de entrada, o tempo de execução e o uso de memória podem aumentar drasticamente (por exemplo, O(n!)).
• Não otimizados: No caso de um grande número de combinações, esses algoritmos podem ser ineficientes e exigir melhorias ou substituição por técnicas mais avançadas (por exemplo, utilização de programação dinâmica ou algoritmos gulosos).

Complexidade temporal e espacial dos algoritmos combinatórios

Complexidade temporal:

• Permutações: O(n!), onde n é o número de elementos do conjunto.
• Combinações: O(C(n, k)), onde C(n, k) é o coeficiente binomial, igual a n! / (k! * (n - k)!).
• Arranjos: O(A(n, k)), onde A(n, k) é o número de arranjos, igual a n! / (n - k)!.
• Subconjuntos: O(2^n), pois cada um dos n elementos pode ser incluído ou não no subconjunto.

Complexidade espacial:

Geralmente O(n) para armazenar resultados intermediários durante a construção recursiva, mas a memória final pode ser necessária para armazenar todos os resultados (por exemplo, O(n * n!) para permutações).

Exemplos de algoritmos combinatórios

8.2 Geração de permutações.

Problema:

Encontrar todas as permutações únicas dos elementos de um conjunto dado.

Algoritmo:

Usa-se métodos recursivos ou iterativos para gerar todas as combinações ordenadas possíveis dos elementos.

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 Geração de combinações

Problema:

Encontrar todas as combinações de tamanho especificado de um conjunto.

Algoritmo:

Usa-se recursão ou iteração para gerar todos os subconjuntos possíveis de tamanho especificado.

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 Geração de partições de conjunto

Problema:

Encontrar todas as maneiras possíveis de dividir um conjunto em subconjuntos.

Algoritmo:

Usa-se recursão para gerar todas as partições possíveis de um conjunto.

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

Usar copy.deepcopy(part[:]) cria uma cópia profunda da lista part.. Isso significa que é criado um novo, independente e não relacionado ao original part.. Assim, cada elemento em result representará uma partição única.