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
Ho realizzato un applet che usa questo algoritmo qui
Codice completo
Il generatore di permutazioni
package darshan.snippet; public class SimplePermutator { public int elementi[]; public int len; public SimplePermutator(int n) { elementi = new int[n]; for (int a = 0; a < n; a++)elementi[a] = a + 1; this.len=n; } private void swap(int a, int b){ int t=elementi[a]; elementi[a]=elementi[b]; elementi[b]=t; } public boolean prossima() { int i = len - 1; while (i>0 && (elementi[i - 1] >= elementi[i])) { i--; } if(i==0)return false; int j = len; while (elementi[j - 1] <= elementi[i - 1])j--; swap(i - 1, j - 1); i++; j = len; while (i < j) { swap(i - 1, j - 1); i++; j--; } return true; } @Override public String toString(){ return Array_util.dump(elementi); } }
il resto del codice
public class Main { public static void main(String[] args) { SimplePermutator p=new SimplePermutator(5); System.out.println("Using "+p.getClass().getName()); do{System.out.println(p.toString());}while(p.prossima()); } }
package darshan.snippet; public abstract class Array_util { static public String dump(int[] elementi) { StringBuffer e = new StringBuffer(); if (elementi.length > 0) { e.append("[ " + elementi[0]); for (int i = 1; i < elementi.length; i++) { e.append(","); e.append(elementi[i]); } } e.append(" ]"); return e.toString(); } }
public int elementi[];
public int len;public SimplePermutator(int n) {
elementi = new int[n];
for (int a = 0; a < n; a++)elementi[a] = a + 1;
this.len=n;
}private void swap(int a, int b){
int t=elementi[a];
elementi[a]=elementi[b];
elementi[b]=t;
}public boolean prossima() {
int i = len – 1;
while (i>0 && (elementi[i - 1] >= elementi[i])) {
i–;
}
if(i==0)return false;
int j = len;
while (elementi[j - 1] <= elementi[i - 1])j–;
swap(i – 1, j – 1);
i++;
j = len;
while (i < j) {
swap(i – 1, j – 1);
i++;
j–;
}
return true;
}@Override
public String toString(){
return Array_util.dump(elementi);
}
}
2 comments
1 ping
fripp
3 luglio 2009 a 08:49 (UTC 2) Link a questo commento
Non ci credo che scrivi codice Java
thedarshan
3 luglio 2009 a 12:03 (UTC 2) Link a questo commento
Questo si prestava… e poi dal Java posso passare velocemente al C#… e questa cosa potrebbe servirmi a breve in C#
Determinare una specifica permutazione dall’insieme delle permutazioni « The Darshan’s Weblog
19 settembre 2009 a 16:27 (UTC 2) Link a questo commento
[...] Determinare una specifica permutazione dall’insieme delle permutazioni questo articolo è la continuazione del articolo precedente sulle permutazioni. [...]