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

Si vous voulez une longueur spécifique de sous-ensembles, vous pouvez procéder comme suit :

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

Plus généralement, pour les sous-ensembles de longueur arbitraire, vous pouvez modifier l'argument de la plage. La sortie est

[(), (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 2

Vous pouvez le faire comme ça :

def powerset(x):
    m=[]
    if not x:
        m.append(x)
    else:
        A = x[0]
        B = x[1:]
        for z in powerset(B):
            m.append(z)
            r = [A] + z
            m.append(r)
    return m

print(powerset([1, 2, 3, 4]))

Salida:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Answer 3

Un moyen simple serait d'exploiter la représentation interne des entiers sous l'arithmétique du complément à 2.

La représentation binaire des nombres entiers est {000, 001, 010, 011, 100, 101, 110, 111} pour les nombres allant de 0 à 7. Pour une valeur de compteur entière, en considérant que 1 est l'inclusion de l'élément correspondant dans la collection et que '0' est l'exclusion, nous pouvons générer des sous-ensembles basés sur la séquence de comptage. Les nombres doivent être générés à partir de 0 a pow(2,n) -1 où n est la longueur du tableau, c'est-à-dire le nombre de bits dans la représentation binaire.

Un simple Fonction de générateur de sous-ensembles basé sur celui-ci peut être écrit comme suit. Il repose essentiellement sur

def subsets(array):
    if not array:
        return
    else:
        length = len(array)
        for max_int in range(0x1 << length):
            subset = []
            for i in range(length):
                if max_int & (0x1 << i):
                    subset.append(array[i])
            yield subset

et ensuite il peut être utilisé comme

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

Essais

Ajout de ce qui suit dans le fichier local

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

donne le résultat suivant

Subsets for  ['b', 'd', 'f']  are  [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for  ['d', 'f']  are  [[], ['d'], ['f'], ['d', 'f']]
Subsets for  ['f']  are  [[], ['f']]

Answer 4

Presque toutes ces réponses utilisent list plutôt que set ce qui m'a semblé être un peu une tricherie. Donc, par curiosité, j'ai essayé de faire une version simple vraiment sur set et résumer pour d'autres personnes "novices en Python".

J'ai trouvé qu'il y avait quelques bizarreries dans l'utilisation de Python. mise en œuvre de l'ensemble . La principale surprise pour moi a été la gestion des ensembles vides. Ceci est en contraste avec l'approche de Ruby Mise en œuvre de l'ensemble où je peux simplement faire Set[Set[]] et obtenir un Set contenant un vide Set donc j'ai trouvé ça un peu confus au début.

Pour revoir, en faisant powerset con set j'ai rencontré deux problèmes :

1. set() prend un itérable, donc set(set()) retournera set() parce que l'ensemble vide itérable est vide (duh je suppose :))
2. pour obtenir un ensemble d'ensembles, set({set()}) y set.add(set) ne fonctionnera pas parce que set() n'est pas hachable

Pour résoudre ces deux problèmes, j'ai fait appel à frozenset() ce qui signifie que je n'obtiens pas tout à fait ce que je veux (le type est littéralement set ), mais fait appel à l'ensemble set interace.

def powerset(original_set):
  # below gives us a set with one empty set in it
  ps = set({frozenset()}) 
  for member in original_set:
    subset = set()
    for m in ps:
      # to be added into subset, needs to be
      # frozenset.union(set) so it's hashable
      subset.add(m.union(set([member]))
    ps = ps.union(subset)
  return ps

En dessous, nous obtenons 2² (16) frozenset correctement en sortie :

In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
 frozenset({3, 4}),
 frozenset({2}),
 frozenset({1, 4}),
 frozenset({3}),
 frozenset({2, 3}),
 frozenset({2, 3, 4}),
 frozenset({1, 2}),
 frozenset({2, 4}),
 frozenset({1}),
 frozenset({1, 2, 4}),
 frozenset({1, 3}),
 frozenset({1, 2, 3}),
 frozenset({4}),
 frozenset({1, 3, 4}),
 frozenset({1, 2, 3, 4})}

Comme il n'y a aucun moyen d'avoir un set de set en Python, si vous souhaitez transformer ces frozenset dans set vous devrez les remettre en correspondance avec un fichier list ( list(map(set, powerset(set([1,2,3,4])))) ) ou modifier ce qui précède.

Answer 5

La question est peut-être un peu ancienne, mais j'espère que mon code pourra aider quelqu'un.

def powSet(set):
    if len(set) == 0:
       return [[]]
    return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])

def addtoAll(e, set):
   for c in set:
       c.append(e)
   return set