Un semplice algoritmo iterativo per listare le permutazioni di un insieme di elementi

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:

1. a partire dall’ultimo elemento scorre l’array cercando il primo elemento preceduto da un elemento minore
2. se non esiste si è giunti all’ultima permutazione possibile e l’algoritmo deve terminare
3. se esiste ricomincia a scorrere il vettore dalla fine cercando il primo elemento maggiore all’elemento trovato al punto1
4. si invertono gli elementi trovati al punto1 e al punto3
5. 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();
 }

}