Spazio delle soluzioni Flashcards
Quali strutture dati si utilizzano tipicamente per le funzioni di calcolo combinatorio?
typedef struct l { int *scelte; int n_scelte; } Livello;
int *val; oppure Livello *val;
int *mark;
int *sol;
Principio di moltiplicazione: esempio
poké: 3 di una, 2 dell’altro, ecc.
32…
Principio di moltiplicazione: codice
int princ_molt(int pos, Livello *val, int *sol, int n, int cnt){
int i;
if(pos >= n){
for(i = 0; i < n; i++) printf(“%d”, sol[i]);
return cnt+1;
}
for(i = 0; i < val[pos].n_scelte; i++){
sol[pos] = val[pos].scelte[i];
cnt = princ_molt(pos+1, val, sol, n, cnt);
}
return cnt;
}
Disposizioni semplici: esempio
Raggruppamento k a k, senza ripetizione
n!/(n-k)!
per esempio: quanti numeri di due cifre distinte si possono formare con 4 cifre totali?
Disposizioni semplici: codice
int dispiace_semplici(int pos, int val, intsol, int *mark, int k, int n, int cnt){ int i;
if(pos >= k){
// stampa sol
return cnt+1;
}
for (i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = disp_sempl(pos + 1, val, sol, mark, k, n, cnt);
mark[i] = 0;
}
}
return cnt;
}
Disposizioni con ripetizione: esempio
elementi k a k, non distinti
n^k;
esempio: quanti sono i numeri binari su 4 bit?
2^4
Disposizioni con ripetizione: codice
int disp_rip(int pos, int * val, int *sol, int n, int k, int cnt){
if (pos>=k){
//stampa sol
return cnt+1;
}
for(i = 0; i < n; i++){
sol[pos] = val[I];
cnt = disp_rip(pos+1, val, sol, n, k, cnt);
}
return cnt;
}
Permutazioni semplici: esempio
n!
Permutazioni con ripetizione: esempio
n!/a!B!…
Permutazioni semplici: codice
int permutazioni_semplici(int pos, int val, intsol, int * mark, int n, int cnt){
if (pos>=n){ // stampa return cnt+1;}
for (int i = 0; i < n; i++){
if (mark[I] == 0){
mark[i] = 1;
sol[pos] = val[I];
cnt = permutazioni_semplici(pos +1, val, sol, mark, n, cnt);
mark[i] = 0;
}
}
return cnt;
}
Permutazioni con ripetizione: codice
int perm_r(int pos, int *dist_val, int n_dist, int *sol, int *mark, int n, int cnt){
if (pos >= n) {
// stampa
return cnt+1;
}
for(int i = 0; i < n_dist; i++){
if(mark[I] > 0){
mark[i]–;
sol[pos] = dist_val[i];
cnt = perm_r(pos+1, dist_val, n_dist, sol, mark, n, cnt);
mark[i]++;
}
}
return cnt;
}
Combinazioni semplici: esempio
in quanti modi si possono stringere la mano 20 persone?
binomiale (20 2)
Combinazioni semplici: codice
int comb_s(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}
for(int i = start; i < n; i ++){
sol[pos] = val[I];
cnt = comb_s(pos+1, val, sol, n, k, I+1, cnt);
}
return cnt;
}
Combinazioni con ripetizione: esempio
Date 5 gocce bianche e 5 nere, quanti colori diversi si possono formare mischiando tra loro 5 gocce prese dai due colori?
binomiale (n+k-1)/k
Combinazioni con ripetizione: codice
int comb_r(int pos, int *val, int *sol, int n, int k, int start, int cnt){
if (pos >= k) {…}
for(i = start; I < n; i++){
sol[pos] = val[I];
cnt = comb_r(pos+1, val, sol, n, k, start, cnt);
}
return cnt;
}
Dato un insieme I, quando i blocchi in cui è diviso sono una sua partizione?
Dato un insieme I e S_i sottoinsiemi ciascuno di k_i elementi, essi sono una partizione di I se:
- ogni blocco non è vuoto
- e sono tutti disgiunti
- e la loro somma dà l’insieme I
Data la partizione di un insieme, l’ordine dei blocchi e degli elementi in essi conta?
NO
Dato un insieme I, quale può essere il numero complessivo di partizioni?
Il numero complessivo di partizioni è definito dai numeri di Bell: 1, 1, 2, 5, 15, 52
Quali modelli ci sono per calcolare l’insieme delle parti?
- paradigma divide et impera
- disposizioni ripetute
- combinazioni semplici
Insieme delle parti con paradigma divide et impera, caratteristiche
per k = 0 viene ritornato l’insieme vuoto, per k > 0 l’insieme delle parti per k elementi è l’insieme delle parti per k-1 elementi a cui decido se aggiungere o meno il kesimo elemento -> due rami ricorsivi distinti
Insieme delle parti con disposizioni ripetute, caratteristiche
- in sol gli elementi sono o 0 o 1 p
- bisogna scegliere se prendere il k-esimo elemento (sol[pos] = 1) oppure no (sol[pos] = 0) e per questo ci sono due rami ricorsivi distinti
Insieme delle parti con combinazioni semplici, caratteristiche
c’è una funzione wrapper che chiama la funzione ricorsiva con k diverso ogni volta (k: numero degli elementi)
Come si possono rappresentare le partizioni di un insieme?
- per ogni elemento si indica il blocco a cui appartiene
- dato ogni blocco se ne elencano gli elementi
Numero casuale di partizioni con disposizioni ripetute
appunti
