«

»

feb 18

Algoritmo degli scambi semplici (Plain changes – Johnson-Trotter)

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

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

n
Factoradic
Permutazione (Semplice)

Permutazione (Plain Changes)

Vettore degli scambi

Vettore delle direzioni

0
0000
[ 1,2,3,4 ]
[ 1,2,3,4 ]
[ 0,0,0,0 ]
----
1
0010
[ 1,2,4,3 ]
[ 1,2,4,3 ]
[ 0,0,0,1 ]
----
2
0100
[ 1,3,2,4 ]
[ 1,4,2,3 ]
[ 0,0,0,2 ]
----
3
0110
[ 1,3,4,2 ]
[ 4,1,2,3 ]
[ 0,0,0,3 ]
----
4
0200
[ 1,4,2,3 ]
[ 4,1,3,2 ]
[ 0,0,1,3 ]
+---
5
0210
[ 1,4,3,2 ]
[ 1,4,3,2 ]
[ 0,0,1,2 ]
-+--
6
1000
[ 2,1,3,4 ]
[ 1,3,4,2 ]
[ 0,0,1,1 ]
--+-
7
1010
[ 2,1,4,3 ]
[ 1,3,2,4 ]
[ 0,0,1,0 ]
---+
8
1100
[ 2,3,1,4 ]
[ 3,1,2,4 ]
[ 0,0,2,0 ]
----
9
1110
[ 2,3,4,1 ]
[ 3,1,4,2 ]
[ 0,0,2,1 ]
----
10
1200
[ 2,4,1,3 ]
[ 3,4,1,2 ]
[ 0,0,2,2 ]
----
11
1210
[ 2,4,3,1 ]
[ 4,3,1,2 ]
[ 0,0,2,3 ]
----
12
2000
[ 3,1,2,4 ]
[ 4,3,2,1 ]
[ 0,1,2,3 ]
++--
13
2010
[ 3,1,4,2 ]
[ 3,4,2,1 ]
[ 0,1,2,2 ]
++--
14
2100
[ 3,2,1,4 ]
[ 3,2,4,1 ]
[ 0,1,2,1 ]
+-+-
15
2110
[ 3,2,4,1 ]
[ 3,2,1,4 ]
[ 0,1,2,0 ]
+--+
16
2200
[ 3,4,1,2 ]
[ 2,3,1,4 ]
[ 0,1,1,0 ]
-+--
17
2210
[ 3,4,2,1 ]
[ 2,3,4,1 ]
[ 0,1,1,1 ]
-+--
18
3000
[ 4,1,2,3 ]
[ 2,4,3,1 ]
[ 0,1,1,2 ]
--+-
19
3010
[ 4,1,3,2 ]
[ 4,2,3,1 ]
[ 0,1,1,3 ]
--+-
20
3100
[ 4,2,1,3 ]
[ 4,2,1,3 ]
[ 0,1,0,3 ]
+--+
21
3110
[ 4,2,3,1 ]
[ 2,4,1,3 ]
[ 0,1,0,2 ]
-+-+
22
3200
[ 4,3,1,2 ]
[ 2,1,4,3 ]
[ 0,1,0,1 ]
--++
23
3210
[ 4,3,2,1 ]
[ 2,1,3,4 ]
[ 0,1,0,0 ]
--++
Permutazioni di un insieme di 4 elementi generate secondo i vari algoritmi descritti
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

Share Button

2 comments

  1. Massimo Minervini

    Ciao Vincenzo!
    Mi presento. Sono da pochi mesi un pensionato IBM, dopo 32 anni di lavoro. Entrai nel “Rome Software Laboratory” IBM nel lontano 1982, in qualità di Ingegnere elettronico. Ho avuto la fortuna di restare sempre nel citato Laboratorio, che – come potrai immaginare – subì tantissime trasformazioni nel corso di un trentennio.
    Ho detto “fortuna” perchè, nonostante il fatto che durante i miei studi universitari avessi “sniffato” più circuiti che argomenti informatici, mi accorsi già nel terzo anno del corso che adoravo scrivere codice (FORTRAN era allora il liguaggio) per risolvere i vari problemi fisici o matematici che si presentavano.
    Bhe’, nel fondato timore che potrei giungere a seccarti coi miei trascorsi, vengo al commento relativo al tuo articolo sui suonatori di campane che idearono l’algoritmo degli scambi semplici.
    Nella tua presentazione, non appare l’idea che ebbero i suonatori di campane… E non traspare affatto dall’implementazione Johnson-Trotter!
    Il miglior articolo che ho trovato sull’argomento è all’indirizzo
    http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
    Ivi, è più chiaro come Johnson-Trotter implementarono il loro algoritmo, MA ANCHE QUì, DOPO UN’OTTIMA DESCRIZIONE SULLA GENERAZIONE DELLE PERMUTAZIONI, NON VIENE CHIARITA L’IDEA ALLA BASE DELL’ALGORITMO JOHNSON/TROTTER…!
    E’ del tutto plausibile che i campanari del secolo decimoquinto misero a punto l’algoritmo in seguito a geniali ma semplici giustificazioni, documentandolo certamente poi in modo chiaro per la mente di ciascuno!
    Una buona documentazione sulle buone idee algoritmiche non dovrebbe mai essere carente!
    In attesa di una tua paziente risposta, ti invio un caro saluto.
    Ing. Massimo Minervini

  2. Vincenzo La Spesa

    Ciao. E’ un piacere conoscere un informatico della generazione precedente. Devi averne viste tante di cose nei 30 anni in cui si è diffusa l’informatica in Italia! Sono sempre stato affascinato dalla storia dell’informatica e in particolare da quella italiana su cui purtroppo si trova poco. Rimpiango di essermi perso il periodo di fidonet e di itapac.

    Ma veniamo alle nostre campane.
    Mi sono procurato Tintinnalogia e voglio leggerlo, così scopriremo come ci sono arrivati.
    http://www.gutenberg.org/ebooks/18567

    Spero che il codice per generare midi funzioni ancora, ci saranno molte campane da suonare.

Commenti disabilitati.