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

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

Answer 2

Il existe 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

Answer 3

TL;DR (aller directement à Simplification)

Je sais que j'ai déjà ajouté une réponse, mais j'aime vraiment ma nouvelle mise en œuvre. Je prends un ensemble en entrée, mais cela peut être n'importe quel itérable, et je renvoie un ensemble d'ensembles qui est l'ensemble puissance de l'entrée. J'aime cette approche parce qu'elle est plus en accord avec la définition mathématique de quantité de puissance ( ensemble de tous les sous-ensembles ).

def power_set(A):
    """A is an iterable (list, tuple, set, str, etc)
    returns a set which is the power set of A."""
    length = len(A)
    l = [a for a in A]
    ps = set()

    for i in range(2 ** length):
        selector = f'{i:0{length}b}'
        subset = {l[j] for j, bit in enumerate(selector) if bit == '1'}
        ps.add(frozenset(subset))

    return ps

Si vous voulez exactement le résultat que vous avez affiché dans votre réponse, utilisez ceci :

>>> [set(s) for s in power_set({1, 2, 3, 4})]
[{3, 4},
 {2},
 {1, 4},
 {2, 3, 4},
 {2, 3},
 {1, 2, 4},
 {1, 2},
 {1, 2, 3},
 {3},
 {2, 4},
 {1},
 {1, 2, 3, 4},
 set(),
 {1, 3},
 {1, 3, 4},
 {4}]

Explication

On sait que le nombre d'éléments de l'ensemble de puissance est de 2 ** len(A) ce qui est clairement visible dans le for boucle.

J'ai besoin de convertir l'entrée (idéalement un ensemble) en une liste car un ensemble est une structure de données d'éléments uniques non ordonnés, et l'ordre sera crucial pour générer les sous-ensembles.

selector est la clé de cet algorithme. Notez que selector a la même longueur que l'ensemble d'entrée, et pour rendre cela possible, il utilise une chaîne f avec un remplissage. En gros, cela me permet de sélectionner les éléments qui seront ajoutés à chaque sous-ensemble lors de chaque itération. Disons que l'ensemble d'entrée comporte 3 éléments {0, 1, 2} Le sélecteur prendra donc des valeurs comprises entre 0 et 7 (inclus), qui sont en binaire :

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

Ainsi, chaque bit pourrait servir d'indicateur pour savoir si un élément de l'ensemble original doit être ajouté ou non. Regardez les nombres binaires, et considérez chaque nombre comme un élément du super ensemble dans lequel 1 signifie qu'un élément à l'indice j doit être ajouté, et 0 signifie que cet élément ne doit pas être ajouté.

J'utilise une compréhension d'ensemble pour générer un sous-ensemble à chaque itération, et je convertis ce sous-ensemble dans un fichier frozenset afin que je puisse l'ajouter à ps (jeu de puissance). Sinon, je ne pourrai pas l'ajouter car un ensemble en Python ne se compose que d'objets immuables.

Simplification

Vous pouvez simplifier le code en utilisant certaines compréhensions python, afin de vous débarrasser de ces boucles for. Vous pouvez également utiliser zip pour éviter d'utiliser j et le code sera le suivant :

def power_set(A):
    length = len(A)
    return {
        frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
        for i in range(2 ** length)
    }

C'est ça. Ce que j'aime de cet algorithme, c'est qu'il est plus clair et plus intuitif que les autres, car il a l'air assez magique pour qu'on puisse s'y fier itertools même s'il fonctionne comme prévu.

Answer 4

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

rendement

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

Answer 5

Cela peut se faire très naturellement avec itertools.product :

import itertools

def powerset(l):
    for sl in itertools.product(*[[[], [i]] for i in l]):
        yield {j for i in sl for j in i}