Data una lista di numeri diversi, per esempio [1,5,2,4], è possibile alterare l’ordine dei suoi elementi scambiando di posto due cifre adiacenti.
Con mosse successive è quindi possibile spostare gli elementi della lista in modo da ottenere la permutazione ordinata crescente; in questo esempio, l’ordinamento si ottiene con due mosse:[1,5,2,4] → [1,2,5,4] → [1,2,4,5].La lista [2,5,4,3] può essere ordinata con tre mosse:
[2,5,4,3] → [2,4,5,3] → [2,4,3,5] → [2,3,4,5].Date le seguenti liste
L1 = [4,9,2,8,3,7],
L2 = [2,1,4,3,6,5,9,7,10,8]Trovare il numero minimo di mosse (N1 e N2 rispettivamente per L1 e L2) necessario per ottenere le corrispondenti permutazioni ordinate crescenti.
Soluzione: 8, 6.
Soluzione
A ogni passo sposto il numero più grande con un certo numero di mosse
L1
| Prima | Dopo | Numero mosse |
| [4,9,2,8,3,7] | [4,2,8,3,7,9] | 4 |
|---|---|---|
| [4,2,8,3,7,9] | [4,2,3,7,8,9] | 2 |
| [4,2,3,7,8,9] | [2,3,4,7,8,9] | 2 |
| 8 | ||
L2
| Prima | Dopo | Numero mosse |
| [2,1,4,3,6,5,9,7,10,8] | [2,1,4,3,6,5,9,7,8,10] | 1 |
|---|---|---|
| [2,1,4,3,6,5,9,7,8,10] | [2,1,4,3,6,5,7,8,9,10] | 2 |
| [2,1,4,3,6,5,7,8,9,10] | [2,1,4,3,5,6,7,8,9,10] | 1 |
| [2,1,4,3,5,6,7,8,9,10] | [2,1,3,4,5,6,7,8,9,10] | 1 |
| [2,1,3,4,5,6,7,8,9,10] | [1,2,3,4,5,6,7,8,9,10] | 1 |
| 6 | ||