Quelle est la bonne façon d'obtenir tous les sous-ensembles d'un ensemble? (powerset)

voici plus de code pour un groupe électrogène. C'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 de 0-length", sauf dans mon cas vous changez for i in range(1 << x) en for i in range(1, 1 << x) .

revenant à ces 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 à ceci, dire:

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

en utilisant yield signifie que vous n'avez pas besoin de calculer tous les résultats dans une seule pièce de mémoire. Le précalcul des masques à l'extérieur de la boucle principale est supposé être une optimisation valable.

si vous cherchez une réponse rapide, j'ai juste cherché "Python power set" sur google et j'ai trouvé ceci: Python Power Set Generator

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

ce qui peut être utilisé comme ceci:

 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ée et imprimée:

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

def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])

Il y a un raffinement de powerset:

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

def get_power_set(s):
  power_set=[[]]
  for elem in s:
    # iterate over the sub sets so far
    for sub_set in power_set:
      # add a new subset consisting of the subset at hand added elem
      power_set=power_set+[list(sub_set)+[elem]]
  return power_set

par exemple:

get_power_set([1,2,3])

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

je voulais juste fournir la solution la plus compréhensible, la version anti code-golf.

from itertools import combinations

l = ["x", "y", "z", ]

def powerset(items):
    combo = []
    for r in range(len(items) + 1):
        #use a list to coerce a actual list from the combinations generator
        combo.append(list(combinations(items,r)))
    return combo

l_powerset = powerset(l)

for i, item in enumerate(l_powerset):
    print "All sets of length ", i
    print item

les résultats

tous les jeux de longueur 0

[()]

tous les jeux de longueur 1

[('x',), ('y',), ('z',)]

tous les jeux de longueur 2

[('x', 'y'), ('x', 'z'), ('y', 'z')]

tous les jeux de longueur 3

[('x', 'y', 'z')]

pour plus voir les docs itertools , aussi l'entrée Wikipédia sur power sets

C'est fou parce qu'aucune de ces réponses fournir le retour d'un véritable Python ensemble. Voici une implémentation désordonnée qui donnera un powerset qui est en fait un Python set .

test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
    """ modified from pydoc's itertools recipe shown above"""
    from itertools import chain, combinations
    base_list = list( base_set )
    combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]

    powerset = set([])
    for ll in combo_list:
        list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) 
        set_of_frozensets = set( list_of_frozensets )
        powerset = powerset.union( set_of_frozensets )

    return powerset

print powerset( test_set )
# >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), 
#        frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']),
#        frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])

j'aimerais voir une meilleure implémentation.

Voici mon implémentation rapide en utilisant des combinaisons mais en n'utilisant que des built-ins.

def powerSet(array):
    length = str(len(array))
    formatter = '{:0' + length + 'b}'
    combinations = []
    for i in xrange(2**int(length)):
        combinations.append(formatter.format(i))
    sets = set()
    currentSet = []
    for combo in combinations:
        for i,val in enumerate(combo):
            if val=='1':
                currentSet.append(array[i])
        sets.add(tuple(sorted(currentSet)))
        currentSet = []
    return sets

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_all_subsets(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

une autre façon de générer le groupe électrogène est de générer tous les nombres binaires qui ont des bits n . Comme un jeu de puissance la quantité de nombre avec n chiffres est 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 pourrait être l'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é les deux algorithmes lorsque je prenais MITx: 6.00.2 X Introduction à la pensée computationnelle et la science des données, et je considère qu'il est l'un des algorithmes les plus faciles à comprendre que j'ai vu.