Insieme parti (powerset)

Insieme delle parti (powerset)

Insieme delle parti (powerset): con il termine powerset si indica l’insieme dei sottoinsiemi dell’insieme di elementi, incluso l’insieme vuoto.

Esempio: dato l’insieme {1, 2, 3}, l’insieme delle parti è {∅, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Per l’approccio algoritmico del calcolo dell’insieme delle parti vi sono tre diverse metodologie:

• Paradigma Divide et Impera: l’insieme delle parti viene trovato ricorsivamente come l’insieme vuoto per il caso terminale e nel caso di ricorsione il powerset per k-1 elementi unione o l’elemento che rappresenta l’insieme stesso di partenza o l’insieme vuoto;
• Utilizzo delle Disposizioni ripetute: l’elemento temporaneamente in utilizzo può essere preso o lasciato quindi si crea un albero della ricorsione che ha come foglie tutti i sottoinsiemi che vanno a formare il powerset;
• Modello spazio delle Combinazioni semplici: si fa l’unione dell’insieme vuoto e dei sottoinsiemi di dimensione da 1 a k crescente ognuno dei quali calcolato con il modello delle combinazioni semplici.

Esempio: algoritmo powerset con disposizioni ripetute

void powerset(int pos, int *val, int *sol, int k){
int i;
if(pos>=k){
printf(“{\t”);
for(i = 0; i if(sol!=0)
printf(“%d\t ”, val);
printf(“}\n”);
return;
}

sol[pos] = 0;
powerset(pos+1, val, sol, k);
sol[pos] = 1;
powerset(pos+1, val, sol, k);
}