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

import math    
def printPowerSet(set,set_size): 
    pow_set_size =int(math.pow(2, set_size))
    for counter in range(pow_set_size):
    for j in range(set_size):  
        if((counter & (1 << j)) > 0):
            print(set[j], end = "")
    print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)

Answer 2

Une variation de la question, est un exercice que je vois sur le livre "Discovering Computer Science : Problèmes interdisciplinaires, principes et programmation Python. 2015 edition". Dans cet exercice 10.2.11, l'entrée est juste un nombre entier, et la sortie devrait être les ensembles de puissance. Voici ma solution récursive (je n'utilise rien d'autre que python3 de base).

def powerSetR(n):
    assert n >= 0
    if n == 0:
        return [[]]
    else:
        input_set = list(range(1, n+1)) # [1,2,...n]
        main_subset = [ ]
        for small_subset in powerSetR(n-1):
            main_subset += [small_subset]
            main_subset += [ [input_set[-1]] + small_subset]
        return main_subset

superset = powerSetR(4)
print(superset)       
print("Number of sublists:", len(superset))

Et la sortie est

[[], [4], [3], [4, 3], [2], [4, 2], [3, 2], [4, 3, 2], [1], [4, 1], [3, 1], [4, 3, 1], [2, 1], [4, 2, 1], [3, 2, 1], [4, 3, 2, 1]] Nombre de sous-listes : 16

Answer 3

Je n'étais pas tombé sur le more_itertools.powerset et je vous recommande de l'utiliser. Je recommande également de ne pas utiliser l'ordre par défaut de la sortie de la fonction itertools.combinations mais souvent, vous souhaitez plutôt minimiser les distance entre les positions et trier les sous-ensembles d'éléments avec une distance plus courte entre eux avant/avant les éléments avec une distance plus grande entre eux.

Le site itertools page des recettes montre qu'il utilise chain.from_iterable

• Notez que le r correspond ici à la notation standard pour la partie inférieure d'une coefficient binomial le s est généralement appelé n dans les textes de mathématiques et sur les calculatrices ("n Choisir r")

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

Les autres exemples ici donnent l'ensemble des pouvoirs de [1,2,3,4] de manière à ce que les 2-tuples soient listés dans l'ordre "lexicographique" (lorsque nous imprimons les nombres comme des entiers). Si j'écris la distance entre les nombres à côté (c'est-à-dire la différence), cela montre mon point de vue :

12  1
13  2
14  3
23  1
24  2
34  1

L'ordre correct pour les sous-ensembles devrait être l'ordre qui "épuise" la distance minimale en premier, comme ceci :

12  1
23  1
34  1
13  2
24  2
14  3

L'utilisation de chiffres donne l'impression que cet ordre n'est pas correct, mais considérez par exemple les lettres suivantes ["a","b","c","d"] on comprend mieux pourquoi il peut être utile d'obtenir l'ensemble des pouvoirs dans cet ordre :

ab  1
bc  1
cd  1
ac  2
bd  2
ad  3

Cet effet est plus prononcé avec un plus grand nombre d'éléments et, dans mon cas, c'est ce qui fait la différence entre la possibilité de décrire les plages d'index de l'ensemble de pouvoirs de manière significative.

(Il y a beaucoup d'écrits sur Codes gris etc. pour l'ordre de sortie des algorithmes en combinatoire, je ne le vois pas comme une question secondaire).

En fait, je viens d'écrire un programme assez complexe qui utilisait ce code de partition rapide d'entiers pour sortir les valeurs dans le bon ordre, mais j'ai ensuite découvert que more_itertools.powerset et pour la plupart des utilisations, il est probablement bien d'utiliser cette fonction comme ça :

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)

J'ai écrit un code plus complexe qui imprimera le jeu de puissance de façon agréable (voir le répertoire pour des fonctions d'impression agréables que je n'ai pas incluses ici : print_partitions , print_partitions_by_length et pprint_tuple ).

• Repo : Ensemble ordonné de puissances et plus particulièrement pset_partitions.py

Tout ceci est assez simple, mais peut être utile si vous voulez un code qui vous permette d'accéder directement aux différents niveaux de l'ensemble de pouvoirs :

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

À titre d'exemple, j'ai écrit un programme de démonstration CLI qui prend une chaîne de caractères comme argument de ligne de commande :

python string_powerset.py abcdef

`a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef` ``

Answer 4

Voici ma solution, elle est similaire (conceptuellement) à la solution de lmiguelvargasf.

Laissez-moi vous dire que -[item mathématique] par définition le powerset ne contient pas l'ensemble vide -[goût personnel] et aussi que je n'aime pas utiliser frozenset.

L'entrée est donc une liste et la sortie sera une liste de listes. La fonction pourrait se fermer plus tôt, mais j'aime que l'élément du jeu de puissance soit l'ordre lexicographiquement qui signifie essentiellement bien.

def power_set(L):
    """
    L is a list.
    The function returns the power set, but as a list of lists.
    """
    cardinality=len(L)
    n=2 ** cardinality
    powerset = []

    for i in range(n):
        a=bin(i)[2:]
        subset=[]
        for j in range(len(a)):
            if a[-j-1]=='1':
                subset.append(L[j])
        powerset.append(subset)

    #the function could stop here closing with
    #return powerset

    powerset_orderred=[]
    for k in range(cardinality+1):
        for w in powerset:
            if len(w)==k:
                powerset_orderred.append(w)

    return powerset_orderred

Answer 5

def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res