Algorithmes combinatoires

8.1 Définition des algorithmes combinatoires.

Les algorithmes combinatoires sont des algorithmes conçus pour résoudre des problèmes liés au comptage, à l'énumération et à la génération de diverses structures combinatoires. Ces algorithmes sont utilisés pour travailler avec des ensembles, des sous-ensembles, des permutations, des combinaisons, et d'autres objets combinatoires.

Principaux types de problèmes combinatoires

• Permutations: Toutes les combinaisons ordonnées possibles d'éléments d'un ensemble.
• Combinaisons: Tous les sous-ensembles possibles non ordonnés d'une taille donnée.
• Arrangements: Tous les sous-ensembles possibles ordonnés d'une taille donnée.
• Partitions: Toutes les manières possibles de diviser un ensemble en sous-ensembles.
• Objets combinatoires: D'autres structures telles que des graphes, des matrices, etc.

Avantages et inconvénients des algorithmes combinatoires

Avantages :

• Énumération complète: Ces algorithmes peuvent énumérer toutes les combinaisons possibles, ce qui est utile pour les problèmes de recherche exhaustive.
• Flexibilité: Ils peuvent être adaptés pour résoudre un large éventail de problèmes liés à la combinatoire.
• Intuitivité: Beaucoup de ces algorithmes sont faciles à comprendre et à mettre en œuvre grâce à l'approche récursive et à la technique de backtracking.

Inconvénients :

• Explosion combinatoire: Avec l'augmentation de la taille des données d'entrée, le temps d'exécution et la quantité de mémoire peuvent augmenter de manière drastique (par exemple, O(n!)).
• Non-optimisation: Dans le cas d'un grand nombre de combinaisons, ces algorithmes peuvent être inefficaces et nécessiter des améliorations ou un remplacement par des techniques plus avancées (par exemple, l'utilisation de la programmation dynamique ou des algorithmes gloutons).

Complexité temporelle et spatiale des algorithmes combinatoires

Complexité temporelle :

• Permutations : O(n!), où n est le nombre d'éléments de l'ensemble.
• Combinaisons : O(C(n, k)), où C(n, k) est le coefficient binomial, égal à n! / (k! * (n - k)!).
• Arrangements : O(A(n, k)), où A(n, k) est le nombre d'arrangements, égal à n! / (n - k)!.
• Sous-ensembles : O(2^n), puisque chaque élément des n éléments peut être inclus ou non dans le sous-ensemble.

Complexité spatiale :

Généralement O(n) pour stocker les résultats intermédiaires lors de la construction récursive, mais la mémoire finale peut être nécessaire pour stocker tous les résultats (par exemple, O(n * n!) pour les permutations).

Exemples d'algorithmes combinatoires

8.2 Génération de permutations.

Problème :

Trouver toutes les permutations uniques des éléments d'un ensemble donné.

Algorithme :

La récursion ou des méthodes itératives sont utilisées pour générer toutes les combinaisons ordonnées possibles des éléments.

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 Génération de combinaisons

Problème :

Trouver toutes les combinaisons d'une taille donnée à partir d'un ensemble.

Algorithme :

La récursion ou l'itération sont utilisées pour générer tous les sous-ensembles possibles d'une taille donnée.

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 Génération de partitions d'un ensemble

Problème :

Trouver toutes les manières possibles de diviser un ensemble en sous-ensembles.

Algorithme :

La récursion est utilisée pour générer toutes les partitions possibles de l'ensemble.

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'utilisation de copy.deepcopy(part[:]) crée une copie profonde de la liste part.. Cela signifie qu'une nouvelle liste indépendante est créée, qui n'est pas liée à l'originale part.. Ainsi, chaque élément dans result représentera une partition unique.