The Darshan’s Weblog

L’algoritmo degli scambi semplici è l’algoritmo più efficiente per generare permutazioni, le permutazioni vengono generate con un singolo scambio, quindi costituiscono un codice Gray.

L’algoritmo è stato ideato nel diciassettesimo secolo in Inghilterra da parte di alcuni suonatori di campane che avevano sviluppato il buffo passatempo di suonare le campane secondo tutte le permutazioni possibili.

Le prime traccie scritte di questo algoritmo risalgono al 1653 ed è trattato in maniera estensiva nel libro Tintinnalogia del 1668 che gli dedica addirittura 60 pagine…Le prime implementazioni informatiche documentate risalgono invece al 1962 ad opera di H. F. Trotter e al 1963 con S.M. Johnson
ed è per questo che l’algoritmo è noto anche come l’algoritmo di Johnson-Trotter.

L’algoritmo opera facendo in modo che solo una coppia venga scambiata ad ogni permutazione e che la coppia sia sempre formata da elementi adiacenti.
L’idea da cui nasce l’algoritmo è che si possano generare le permutazioni di un vettore di n elementi scegliendo dei sottovettori di n-1 elementi e facendo scorrere l’n-esimo elemento all’interno dei sottovettori.
Quando l’n-esimo ha percorso l’intero sottovettore, si calcola la prossima permutazione del sottovettore e si fa scorrere l’n-esimo elemento in senso contrario.
Per implementare questa procedura si usa un secondo vettore che contiene le direzioni di mobilità possibili (il vettore D) che vengono settate a 1 (mobile a destra) o a -1 (mobile a sinistra).
Un singolo elemento è mobile soltanto se nella direzione della sua mobilità (vettore D) l’elemento successivo è inferiore dell’elemento corrente (in particolare il primo elemento non è mai mobile a sinistra e l’ultimo non è mai mobile a destra).
Si usa inoltre un vettore degli scambi (vettore C) il cui n-esimo elemento rappresenta il numero di elementi minori di n che stanno alla sua destra. Confrontando le variazioni del vettore C con la direzione di mobilità contenuta nel vettore D si può ottenere lo scambio da eseguire per arrivare alla permutazione successiva.

a questo punto l’algoritmo agisce in questo modo:

Finchè esistono elementi mobili se ne trova il maggiore e lo si inverte con l’elemento successivo nella direzione di mobilità e si inverte la direzione di mobilita di tutti gli elementi alla sua destra

Esecuzione dell'algoritmo degli scambi semplici su un insieme di 4 elementi

public  void list_all(){
	 int n=this.len;
	 do{
		 flag=true;
		 System.out.println(Array_util.dump(elementi));
		 j=n-1;
		 s=0;
		 do{
			 q=c[j]+d[j];
			 if(q==1 && j==0)return;
			 if(q>=0 && q!=(j+1)){
				 Array_util.swap(elementi, j-c[j]+s, j-q+s);
				 c[j]=q;
				 flag=false;
			 }else{
				 if(q==j+1)s++;
				 if(q<0 || q==j+1){
					 d[j]=-d[j];
					 j--;
				}
			 }
		 }while(flag);
	 }while(true);
}

ma la parte divertente deve ancora arrivare: ho fatto suonare l’algoritmo su una scala pentatonica e ne ho generato un midi