Spesso quando si lavora su algoritmi che hanno come dati di ingresso una lista di elementi si ha la necessità di testarne il comportamento su tutte le permutazioni possibili dell’insieme di ingresso.
L’algoritmo seguente è probabilmente il più semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi, l’algoritmo analizza semplicemente la permutazione attuale per ricavarne la prossima basandosi sul fatto che le permutazioni devono seguire un ordinamento lessicografico (nel caso numerico qui analizzato ogni permutazione deve essere la minima permutazione maggiore di quella corrente)
public boolean prossima() {
int i = len - 1;
while (i>0 && (elementi[i - 1] >= elementi[i])) {
i--;
}
if(i==0)return false;
int j = len;
// (i-1) è l'elemento trovato con il ciclo precedente
while (elementi[j - 1] < = elementi[i - 1])j--;
swap(i - 1, j - 1);
i++;
j = len;
//inverto gli elementi tra i due elementi scambiati
while (i < j) {
swap(i - 1, j - 1);
i++;
j--;
}
return true;
}
considerando la permutazione come un vettore di n elementi numerici l’algoritmo determina la permutazione successiva nel seguente modo:
- a partire dall’ultimo elemento scorre l’array cercando il primo elemento preceduto da un elemento minore
- se non esiste si è giunti all’ultima permutazione possibile e l’algoritmo deve terminare
- se esiste ricomincia a scorrere il vettore dalla fine cercando il primo elemento maggiore all’elemento trovato al punto1
- si invertono gli elementi trovati al punto1 e al punto3
- se lo scambio non è avvenuto tra elementi di livello minimo (l’ultimo e il penultimo) si ripristina l’ordinamento interno invertendo le posizioni degli elementi che si trovano tra l’elemento trovato al punto1 e quello trovato al punto3
l’algoritmo è molto semplice e molto generico ma non è efficiente, infatti il fatto di dover analizzare a ogni iterazione la struttura attuale del vettore ne incrementa di molto la complessità.
Un modo per rendere molto più efficiente l’algoritmo è quello di dotare l’algoritmo di un altro vettore che contiene dati sulla struttura attuale del vettore degli elementi in modo da poter determinare velocemente la prossima permutazione.
Un altro miglioramento notevole si può ottenere evitando che a uno scambio debba seguire una ristrutturazione del vettore, entrambe queste ottimizazioni sono implementate nell algoritmo di Johnson–Trotter
Quando si sviluppa un applicazione che permette di interagire e modificare un database (quelle che oggi fa tanto figo chiamare CRUD) può essere utile prevedere una funzione che permetta di effettuare velocemente e con un solo click il backup completo dell’intero database (dati, struttura, trigger e stored procedure).
IC alle 13.29 del 19 giugno
diciamo ke è anke un modo per fare ” curtigghiu “!!
VLS alle 13.58 del 19 giugno
dico che è ESCLUSIVAMENTE un modo per fare curtigghiu.
I gruppi sono inutilizzabili, perche uno finisce per averne troppi e non seguirne nessuno, anche perche non hanno notifiche ne rss.
E’ tutto basato sulla bacheca dove i commenti scivolano via spinti da altro curtigghiu, è impossibile farci una discussione seria e duratura (che duri il tempo necessario per svilupparsi).
Comincio a pensare che il prodotto qualità*quantità dei siti sia costante…lo diceva umberto eco molti anni fà prima che si cominciasse a parlare di web2.0
E una degenerazione: prima un sito lo aveva solo chi sapeva gestirlo, poi si sono diffusi i blog dove anche chi non saprebbe creare o gestire un sito piò averne uno e poi sono arrivati questi social network “asociali” dove anche chi è troppo lagnuso per avere un blog può scrivere e avere un feedback anche se scrive banalità.
MS alle 14.00 del 19 giugno
W il bar!