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<k; 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);
}

Hai bisogno di aiuto in Informatica?
Trova il tuo insegnante su Skuola.net | Ripetizioni
Registrati via email