Liste ordinate

[axpgn]

Supponiamo di avere una lista composta dai numeri $1, 2, 3, 4, 5, 6, 7, 8, 9$ disposti in qualche ordine e nella quale ogni numero compare esattamente una volta.
Il nostro compito è quello di mettere in ordine crescente la lista usando la procedura seguente.
Confrontiamo i numeri in prima e seconda posizione.
Se sono in ordine crescente, non facciamo niente; se non lo sono li scambiamo di posto.
Ora confrontiamo i numeri in seconda e terza posizione; come prima, li scambiamo solo se non sono in ordine crescente.
Continuando in questo modo, alla fine confrontiamo i numeri in ottava e nona posizione, scambiandoli se necessario.
Questa procedura non sempre crea una lista completamente ordinata (p.es. lista originale $2, 1, 3, 4, 9, 6, 5, 7, 8$ e lista dopo la procedura $1, 2, 3, 4, 6, 5, 7, 8, 9$).

Quante sono le differenti liste originali che vengono ordinate in modo crescente usando la nostra procedura?


Cordialmente, Alex

[Quinzio]

Testo nascosto, fai click qui per vederlo

Quesito molto piu' umano rispetto alla somma criptata.

In tutto vengono fatti 8 confronti. Ogni confronto puo' dare luogo a uno scambio oppure no.
Traducendo lo scambio in una cifra binaria 0,1, ci si ritrova con un numero binario da 8 cifre.
Ergo ci sono $2^8=256$ liste che vengono ordinate da questo metodo.
Per convincersi di questa risposta si puo' pensare di prendere la lista ordinata e di fare gli scambi a ritroso, partendo dall'ultima cifra, il 9, e andando verso l'inizio, facendo lo scambio se la sequenza binaria (a ritroso) lo prevede.
Otteniamo cosi' una lista non ordinata (a meno che non sia stato fatto alcun scambio).
Applicando la procedura (nel verso giusto) a questa lista non ordinata e' garantito(*) che si torni alla lista ordinata con gli stessi scambi.

(*): Si spera che sia cosi'

Tra l'altro questa procedura e' la prima spazzolata fatta dall'algoritmo di ordinamento "bubble sort".
https://it.wikipedia.org/wiki/Bubble_sort
Per oggi basta cosi'.

[axpgn]

Cordialmente, Alex