Problema dell'ordinamento attraverso le inversioni

Il problema dell'ordinamento attraverso le inversioni è simile al problema della distanza inversa, salvo il fatto che richiede solo un'unica permutazione come input (mentre nel problema della distanza inversa erano 2).

 

Lo scopo di questo problema è quello di effettuare una permutazione, e trovare le serie di inversioni più breve che la trasformano nella stessa permutazione (1 2 … n ).

 L’input è la permutazione π, mentre l’output è una serie di inversioni ρ1, … ρt che trasformano π nella stessa permutazione in modo che t sia la minima.

 

In questo caso chiamiamo t la distanza inversa di π e indichiamo esso come d(π). Quando ordiniamo una permutazione π = 1 2 3 6 4 5, è difficile dare un senso al movimento dei primi tre elementi di π che sono già ordinati. Se definiamo il prefix (π) come il numero di elementi già ordinati presenti all’interno di π, allora una buona strategia dell’ordinamento da inversione è di aumentare il prefix (π) ad ogni passaggio. Questo approccio permette di ordinare π in 2 passaggi:

 

1 2 3 6 4 5 → 1 2 3 4 6 5  → 1 2 3 4 5 6.

 

generalizzando quanto appena detto arriviamo ad un algoritmo che ordina una permutazione attraverso spostamenti ripetuti del suo elemento i-esimo alla i-esima posizione.

 

 

SimpleReversalSort (π)

1.      for i ← 1  to  n -1

2.             j ← posizione dell’elemento i in π (es.: πj = i)

3.             if j ≠ i

4.                    π ← π ∙ ρ(i, j)

5.                    output π

6.             if π è la permutazione identità

7.                    return

 

 

il “SimpleReversalSort ” è un esempio di algoritmo di greedy che sceglie la “migliore” inversione ad ogni passaggio. Comunque, la nozione “migliore” è qui accennata, semplicemente aumentando il prefix (π) non si garantisce di individuare il più piccolo numero di inversioni. Per esempio SimpleReversalSort prende 5 passi per ordinare 6 1 2 3 4 5:

 

 6 1 2 3 4 5 → 1 6 2 3 4 5 → 1 2 6 3 4 5 → 1 2 3 6 4 5 → 1 2 3 4 6 5 → 1 2 3 4 5 6.

 

Tuttavia, la stessa permutazione può essere ordinata in solo 2 passi:

 

 6 1 2 3 4 5 → 5 4 3 2 1 6 → 1 2 3 4 5 6

 

Tuttavia possiamo dire che SimpleReversalSort non è un algoritmo corretto in senso stretto. Infatti, a dispetto del senso comune, SimpleReversalSort è un algoritmo terribile da quando prende n-1 passi ordina la permutazione π  =  n 1 2 . . . (n - 1) seppure d(π) = 2.