Partizionamenti in C

Partizionamenti in C

Sia dato un insieme di n elementi, allora una collezione di blocchi non vuoti forma una partizione soltanto se i blocchi sono a coppie disgiunte (la loro intersezione sia vuota), e che l’unione di tutti i blocchi dia l’insieme di partenza. Inoltre l’ordine dei blocchi e degli elementi all’interno non conta, partizioni ordinate diversamente vengono considerate identiche.
Il numero di blocchi della partizione può variare da un minimo di un blocco a n blocchi (blocchi separati per ogni elemento dell’insieme di partenza).
Il numero complessivo delle possibili diverse partizioni di un insieme si ricava dai numeri di Bell.
Esistono diversi approcci per il calcolo delle partizioni di un insieme, che si differenziano dal trovare tutte le partizioni, le partizioni con k blocchi con k fissato, evitando le soluzioni simmetriche o comprendendole. Esempi di metodologie per il calcolo delle partizioni sono l’uso delle disposizioni ripetute e l’algoritmo di Er.

Esempio: algoritmo di Er per trovare tutte le partizioni di un insieme

void ER(int n, int m, int pos, int *sol, int *val){
int i, j;
if(pos>=n){
printf(“partizione in %d blocchi: ”, m);
for(i = 0; i for(j = 0; j if(sol[j] == i)
printf(“%d ”, val[j]);
printf(“\n”);
return
}
for(i = 0; i sol[pos] = i;
ER(n, m, pos+1, sol, val);
}
sol[pos] = m;
ER(n, m+1, pos+1, sol, val);
}