Algoritmos combinatorios

8.1 Definición de los algoritmos combinatorios.

Algoritmos combinatorios — son algoritmos diseñados para resolver problemas relacionados con el conteo, enumeración y generación de varias estructuras combinatorias. Estos algoritmos se utilizan para trabajar con conjuntos, subconjuntos, permutaciones, combinaciones y otros objetos combinatorios.

Tipos principales de problemas combinatorios

• Permutaciones: Todas las combinaciones ordenadas posibles de los elementos de un conjunto.
• Combinaciones: Todos los subconjuntos posibles no ordenados de un tamaño dado.
• Disposiciones: Todos los subconjuntos ordenados posibles de un tamaño dado.
• Particiones: Todas las formas posibles de dividir un conjunto en subconjuntos.
• Objetos combinatorios: Otras estructuras, como grafos, matrices, etc.

Ventajas y desventajas de los algoritmos combinatorios

Ventajas:

• Enumeración completa: Estos algoritmos pueden enumerar todas las combinaciones posibles, lo que es útil para tareas de búsqueda exhaustiva.
• Flexibilidad: Pueden adaptarse para resolver una amplia gama de problemas relacionados con la combinatoria.
• Intuitivos: Muchos algoritmos son fáciles de entender e implementar gracias al enfoque recursivo y la técnica de rastreo inverso (backtracking).

Desventajas:

• Explosión combinatoria: A medida que el tamaño de los datos de entrada crece, el tiempo de ejecución y el espacio de memoria pueden aumentar drásticamente (por ejemplo, O(n!)).
• No óptimos: En el caso de un gran número de combinaciones, estos algoritmos pueden ser ineficaces y requerir mejoras o sustitución por técnicas más avanzadas (como el uso de programación dinámica o algoritmos voraces).

Complejidad temporal y espacial de los algoritmos combinatorios

Complejidad temporal:

• Permutaciones: O(n!), donde n es el número de elementos del conjunto.
• Combinaciones: O(C(n, k)), donde C(n, k) es el coeficiente binomial, igual a n! / (k! * (n - k)!).
• Disposiciones: O(A(n, k)), donde A(n, k) es el número de disposiciones, igual a n! / (n - k)!.
• Subconjuntos: O(2^n), ya que cada uno de los n elementos puede ser incluido o no en el subconjunto.

Complejidad espacial:

Generalmente O(n) para almacenar resultados intermedios durante el proceso de construcción recursiva, pero la memoria final puede ser necesaria para almacenar todos los resultados (por ejemplo, O(n * n!) para permutaciones).

Ejemplos de algoritmos combinatorios

8.2 Generación de permutaciones.

Problema:

Encontrar todas las permutaciones únicas de los elementos de un conjunto dado.

Algoritmo:

Se utilizan métodos recursivos o iterativos para generar todas las combinaciones ordenadas posibles de los 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 Generación de combinaciones

Problema:

Encontrar todas las combinaciones de un tamaño dado de un conjunto.

Algoritmo:

Se utiliza recursión o iteración para generar todos los subconjuntos posibles de un tamaño dado.

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 Generación de particiones de un conjunto

Problema:

Encontrar todas las formas posibles de dividir un conjunto en subconjuntos.

Algoritmo:

Se utiliza recursión para generar todas las particiones posibles de un 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}))
        
        

El uso de copy.deepcopy(part[:]) crea una copia profunda de la lista part. Esto significa que se crea una nueva lista independiente que no está vinculada al part original. Así, cada elemento en result representará una partición única.