[Python Powerset] Comment obtenir tous les sous-ensembles d'un ensemble ?

Il s'agit d'un algorithme simple pour trouver tous les ensembles de puissances d'un ensemble donné. Si vous sentez que vous avez besoin de rafraîchir vos compétences sur les ensembles Python, consultez mon guide complet sur les ensembles Python (avec des exemples de Harry Potter).

Formulation du problème :Powerset

Quel est le powerset d'un ensemble donné s ?

Le powerset est l'ensemble de tous les sous-ensembles de l'ensemble donné s .

Un sous-ensemble est un ensemble qui inclut un nombre arbitraire d'éléments de l'ensemble d'origine s . Il comprend à la fois l'ensemble vide {} et l'ensemble donné s .

Jetez un œil aux exemples suivants :

Exemple 1 :

Ensemble donné :s = {1}
Powerset :P = {{},{1}}

Exemple 2 :

Ensemble donné :s = {1, 2}
Powerset :P = {{},{1},{2},{1,2}}

Exemple 3 :

Ensemble donné :s = {1, 2, 3}
Powerset :P = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Idée d'algorithme itératif

Dans les exemples précédents, pouvez-vous déjà voir le modèle de construction de l'ensemble de pouvoirs de manière itérative ?

Pour calculer un powerset P d'un ensemble s avec n éléments, calculez simplement le powerset P' d'un sous-ensemble de s avec (n-1) éléments et ajoutez le n -ème élément à chaque ensemble dans le powerset P' .

Fusionnez maintenant l'ensemble d'ensembles résultant avec le powerset précédent P' et vous obtenez le powerset P .

En d'autres termes, commencez par l'ensemble vide {} et placez-le dans un ensemble temporaire d'ensembles P' . Passez maintenant sur tous les éléments x en s . Pour chaque élément x et chaque ensemble p en P' , créez un nouveau sous-ensemble composé de l'union de x et p .

Cette stratégie sera expliquée en détail dans ce qui suit.

Powerset en tant que Python One-Liner

Nous considérons le problème suivant :Créer une solution à une ligne qui calcule le powerset d'un ensemble donné s .

Voici le code, nous vous l'expliquerons juste après :

# Dependencies
from functools import reduce


# The Data
s = {1, 2, 3}


# The One-Liner
ps = lambda s: reduce(lambda P, x: P + [subset | {x} for subset in P], s, [set()])


# The Result
print(ps(s))

Liste :solution à une ligne utilisant l'arithmétique de tableau de base.

🧩 Exercice :Devinez le résultat de cet extrait de code !

Le one-liner montre une manière élégante de résoudre le problème du calcul du powerset.

L'idée est de démarrer le powerset comme un ensemble vide et d'y ajouter à plusieurs reprises des sous-ensembles jusqu'à ce qu'il ne puisse plus en trouver.

Initialement, seul l'ensemble vide est dans le powerset.

Maintenant, à chaque étape, nous prenons un élément x hors du jeu de données s et créez un tas de nouveaux sous-ensembles qui émergent naturellement en ajoutant x à tous les sous-ensembles qui sont déjà dans le powerset. Par conséquent, la taille du powerset double chaque fois que nous ajoutons un nouvel élément x .

De cette façon, nous pouvons développer le powerset un élément à la fois.

Le one-liner utilise le reduce( ) fonction pour accomplir cette idée. Il maintient le powerset actuel dans la variable P (qui ne contient initialement que l'ensemble vide).

En utilisant la compréhension de liste, il crée de nouveaux sous-ensembles - un pour chaque sous-ensemble existant - et les ajoute au powerset P . En particulier, il ajoute la valeur x du jeu de données à chaque sous-ensemble et double ainsi la taille du powerset (contenant les sous-ensembles avec et sans l'élément de jeu de données x ).

De cette manière, le reduce() la fonction « fusionne » à plusieurs reprises deux éléments :le powerset P et un élément x du jeu de données.

Par conséquent, le résultat de la ligne unique est le suivant :

# The Result
print(ps(s))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Cet article est basé sur une section livre de mon livre NoStarch 2021. Je vais vous montrer plus de façons de calculer le powerset dans un instant.

Mais avant de continuer, je suis ravi de vous présenter mon nouveau livre Python Python One-Liners (Lien Amazon).

Si vous aimez les one-liners, vous allez adorer le livre. Il vous apprendra tout ce qu'il y a à savoir sur une seule ligne de code Python. Mais c'est aussi une introduction à l'informatique , science des données, apprentissage automatique et algorithmes. L'univers en une seule ligne de Python !

Le livre est sorti en 2020 avec l'éditeur de livres de programmation de classe mondiale NoStarch Press (San Francisco).

Lien :https://nostarch.com/pythononeliners

Itertools Python Powerset

Pour calculer le powerset, vous pouvez utiliser le itertools bibliothèque comme suit :

Importer le chain et combinations sous-modules.
Utiliser une expression de générateur combinations(s, r) for r in range(len(s)+1) pour générer toutes les combinaisons de r -longueur des sous-séquences de s pour toutes les valeurs possibles de r . En savoir plus sur la fonction de combinaisons ici.
Fusionnez tous ceux-ci en une seule liste en utilisant le chain.from_iterable() fonction autour de l'expression du générateur précédent.

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


results = list(powerset(['alice', 'bob', 'carl']))
print(results)
# [(), ('alice',), ('bob',), ('carl',), ('alice', 'bob'), ('alice', 'carl'), ('bob', 'carl'), ('alice', 'bob', 'carl')]

Référence :Vous pouvez en savoir plus sur cette idée ici.

Python Powerset récursif

L'algorithme suivant calcule récursivement le powerset récursivement :

Cas de base de la récursivité :Si la liste initiale est vide, elle renvoie le "powerset" trivial [[]] .
Calcul récursif :Si la liste initiale n'est pas vide, calcule récursivement le powerset de la sous-liste à partir du deuxième élément.
Construire la solution de niveau supérieur :Créez une deuxième liste de sous-listes en ajoutant le premier élément à chaque élément dans le powerset créé de manière récursive. Maintenant, combinez les deux listes optées avec le powerset.

def powerset(lst):
    if not lst:
        return [[]]
    exclude_first = powerset(lst[1:])
    include_first = [[lst[0]] + x for x in exclude_first]
    return exclude_first + include_first


s = powerset(['alice', 'bob', 'carl'])
print(s)
# [[], ['carl'], ['bob'], ['bob', 'carl'], ['alice'], ['alice', 'carl'], ['alice', 'bob'], ['alice', 'bob', 'carl']]

Notez que vous pouvez facilement modifier la liste résultante de la liste en un ensemble de tuples pour représenter de manière plus appropriée la structure de données "powerset".