Comment obtenir tous les sous-ensembles d'un ensemble ? (powerset)

Question

Étant donné un ensemble

{0, 1, 2, 3}

Comment puis-je produire les sous-ensembles :

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

Answer 1

Le Python itertools page a exactement un powerset recette pour ça :

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

Salida:

>>> 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')]

Si vous n'aimez pas ce tuple vide au début, vous pouvez simplement modifier le paramètre range déclaration à range(1, len(s)+1) pour éviter une combinaison de longueur 0.

Answer 2

Voici plus de code pour un powerset. Ceci est écrit à partir de zéro :

>>> def powerset(s):
...     x = len(s)
...     for i in range(1 << x):
...         print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]

Le commentaire de Mark Rushakoff est applicable ici : "Si vous n'aimez pas ce tuple vide au début, on. "vous pouvez simplement changer l'instruction range en range(1, len(s)+1) pour éviter une combinaison 0-length", sauf que dans mon cas vous changez for i in range(1 << x) a for i in range(1, 1 << x) .

---

En y revenant des années plus tard, je l'écrirais maintenant comme ceci :

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

Et alors le code de test ressemblerait à ça, disons :

print(list(powerset([4, 5, 6])))

Utilisation de yield signifie que vous n'avez pas besoin de calculer tous les résultats dans un seul morceau de mémoire. On suppose que le précalcul des masques en dehors de la boucle principale est une optimisation intéressante.

Answer 3

Si vous cherchez une réponse rapide, j'ai cherché "python power set" sur Google et j'ai trouvé ceci : Groupe électrogène Python

Voici un copier-coller du code de cette page :

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

Cela peut être utilisé comme suit :

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

Maintenant r est une liste de tous les éléments que vous vouliez, et peut être trié et imprimé :

r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]

Answer 4

Fonction d'utilisation powerset() du paquet more_itertools .

Donne tous les sous-ensembles possibles de l'itérable.

list(powerset([1, 2, 3])) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Si vous voulez des ensembles, utilisez :

list(map(set, powerset(iterable)))

Answer 5

J'ai trouvé l'algorithme suivant très clair et simple :

def get_powerset(some_list):
    """Returns all subsets of size 0 - len(some_list) for some_list"""
    if len(some_list) == 0:
        return [[]]

    subsets = []
    first_element = some_list[0]
    remaining_list = some_list[1:]
    # Strategy: get all the subsets of remaining_list. For each
    # of those subsets, a full subset list will contain both
    # the original subset as well as a version of the subset
    # that contains first_element
    for partial_subset in get_powerset(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

Une autre façon de générer le jeu de puissances est de générer tous les nombres binaires qui ont n bits. En tant que puissance fixée, la quantité de nombre avec n Les chiffres sont 2 ^ n . Le principe de cet algorithme est qu'un élément peut être présent ou non dans un sous-ensemble comme un chiffre binaire peut être un ou zéro mais pas les deux.

def power_set(items):
    N = len(items)
    # enumerate the 2 ** N possible combinations
    for i in range(2 ** N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

J'ai trouvé ces deux algorithmes lorsque je suivais le cours MITx : 6.00.2x Introduction à la pensée computationnelle et à la science des données, et je considère que c'est l'un des algorithmes les plus faciles à comprendre que j'ai vu.