Trova Powerset in Python

Hemank Mehtani 30 gennaio 2023
  1. Usa l’approccio iterativo per ottenere un Powerset in Python
  2. Usa la funzione itertools.combinations per trovare un Powerset in Python
  3. Usa il metodo di comprensione delle liste per trovare un Powerset in Python
  4. Usa il metodo ricorsivo per trovare un Powerset in Python
Trova Powerset in Python

In matematica, un insieme di potenze di qualsiasi insieme è un insieme che contiene tutti i possibili sottoinsiemi di un dato insieme insieme a un insieme vuoto. In altre parole, tutti i sottoinsiemi di un insieme sono anche conosciuti come powerset. In Python può esserci un insieme potente di elenchi, insiemi, stringhe, ecc.

In questo tutorial, troveremo il set di potenza di un dato set in Python.

Usa l’approccio iterativo per ottenere un Powerset in Python

Sebbene possiamo usare sia l’approccio ricorsivo che l’approccio iterativo per trovare un powerset, l’approccio iterativo è preferito rispetto a quello ricorsivo in quanto è un processo più veloce.

Usiamo un cicli for annidato per creare un tale powerset.

Per esempio,

def powerset(fullset):
    listsub = list(fullset)
    subsets = []
    for i in range(2 ** len(listsub)):
        subset = []
        for k in range(len(listsub)):
            if i & 1 << k:
                subset.append(listsub[k])
        subsets.append(subset)
    return subsets


subsets = powerset(set([1, 2, 3, 4]))
print(subsets)
print(len(subsets))

Produzione:

[[], [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]]
16

Usa la funzione itertools.combinations per trovare un Powerset in Python

itertools è un modulo in Python utilizzato per iterare su strutture di dati. Queste strutture di dati sono anche note come iterabili. Possono essere scavalcati usando il bucle for.

La funzione combinations di questo modulo può creare combinazioni di un set per creare un powerset.

Vedi il codice qui sotto.

from itertools import combinations


def powerset(string):
    n = len(string)
    for i in range(0, n + 1):
        for element in combinations(string, i):
            print("".join(element))


string = ["x", "y", "z"]
powerset(string)

Produzione:

x
y
z
xy
xz
yz
xyz

Usa il metodo di comprensione delle liste per trovare un Powerset in Python

Comprensione delle liste è un modo per creare nuovi elenchi basati sull’elenco esistente. Offre una sintassi più breve essendo più compatta e veloce rispetto alle altre funzioni e cicli utilizzati per creare un elenco.

Usiamo un cicli for annidato anche in questo metodo.

Per esempio,

def get_subsets(fullset):
    listrep = list(fullset)
    n = len(listrep)
    return [[listrep[k] for k in range(n) if i & 1 << k] for i in range(2 ** n)]


string = ["x", "y", "z"]
print(get_subsets(string))

Produzione:

[[], ['x'], ['y'], ['x', 'y'], ['z'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']]

Usa il metodo ricorsivo per trovare un Powerset in Python

Il metodo ricorsivo è un metodo in cui una funzione continua a invocare se stessa con argomenti diversi. Possiamo creare una funzione ricorsiva per trovare il powerset di un insieme.

Per esempio,

def powerSet(string, index, c):
    if index == len(string):
        print(c)
        return
    powerSet(string, index + 1, c + string[index])
    powerSet(string, index + 1, c)


s1 = ["a", "b", "c"]
index = 0
c = ""
powerSet(s1, index, c)

Produzione:

abc
ab
ac
a
bc
b
c

Articolo correlato - Python Set