Comment puis-je générer efficacement tous les sous-ensembles (Powerset) d'un ensemble donné en Python ?

Recherche de tous les sous-ensembles d'un ensemble : le Powerset

Étant donné un ensemble d'éléments, trouver tous ses sous-ensembles peut être une tâche de programmation courante . C'est ce qu'on appelle la construction de l'ensemble de puissances de l'ensemble.

Solution utilisant itertools

Le module Python itertools fournit une solution élégante pour calculer l'ensemble de puissances à l'aide de combinaisons :

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Comment ça marche

Cette fonction génère tous combinaisons d'éléments dans l'ensemble, d'un ensemble vide à l'ensemble complet. Il y parvient en itérant sur la plage de tailles de sous-ensembles possibles (de 0 au nombre d'éléments dans l'ensemble) et en créant des combinaisons d'éléments pour chaque taille.

Exemple

Par exemple, l'ensemble des puissances de l'ensemble {0, 1, 2, 3} est :

list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

Personnalisation

Si vous souhaitez exclure le sous-ensemble vide de l'ensemble de puissances, vous pouvez modifier l'instruction range dans la fonction powerset en range(1 , lentille(s) 1) :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!