Non hai specificato in che linguaggio ti interessa, per cui ti daro' l'algoritmo in python
.
E' abbastanza semplice se lo pensi in modo ricorsivo, partendo dal caso piu' semplice e aggiungendo man mano elementi.
I sottoinsiemi dell'insieme vuoto e' dato dall'insieme contenente solo l'insieme vuoto.
A questo punto, se abbiamo i sottoinsiemi P(X) di un insieme X, i sottoinsiemi di X u {x} sono dati da P(X) u { {x} u Y | Y in P(X) }, ovvero utti i sottoinsiemi di X piu' tutti i sottoinsiemi di X a cui abbiamo aggiunto il nuovo elemento.
La "traduzione" in algoritmo e' immediata (te la faccio in python per semplicita'):
Codice:
def subsets(x):
if x == []:
return [[]]
else:
subs = subsets(x[1:])
return subs + [ [x[0]] + xs for xs in subs ]