Permutazioni e superscambi

[orsoulx]

Data una stringa di $ n $ elementi diversi, si può ottenere una qualsiasi sua permutazione con, al più, $ n-1 $ scambi.
Supponiamo sia possibile eseguire più scambi contemporaneamente con quello che chiamiamo superscambio; naturalmente un singolo elemento può comparire al massimo una volta in un superscambio.
Quanti superscambi occorrono, al massimo, per ottenere una qualsiasi permutazione di $ n $ elementi?
Assegnata la permutazione, quale algoritmo permette di individuare i superscambi necessari?
Ciao
B.

[axpgn]

Alcune considerazioni ...

Data una permutazione qualsiasi di $n$ elementi, se ha un solo elemento al posto "giusto", gli scambi necessari per rimetterla a posto sono gli stessi che servono per una stringa di $n-1$ elementi, quindi ci interessiamo solo delle dismutazioni.
Nel primo passo per "riordinarla" è possibile mettere a posto almeno la metà degli elementi (o meglio $\lfloor n/2\rfloor$) con $\lfloor n/2\rfloor$ scambi e un solo superscambio; nel secondo passo almeno la metà della metà e così via ...
I superscambi dovrebbero quindi essere pari all'incirca al logaritmo in base $2$ di $n$

Cordialmente, Alex

[orsoulx]

@Alex

Direi che le tue considerazioni siano corrette. Però si può dimostrare che, almeno per $ n>4 $, bastino meno superscambi.

Ciao
B.

[axpgn]

Passi avanti ...

Prendiamo una permutazione qualsiasi e analizziamo la prima posizione, che chiameremo posizione $A$; se contiene l'oggetto $a$ siamo a posto, altrimenti poniamo che contenga il generico oggetto $k$, allora andiamo a vedere cosa contiene la posizione $K$: se contiene $a$, li scambiamo e siamo a posto, in caso contrario conterrà il generico oggetto $h$.
In questo caso andremo a scambiare l'oggetto $k$ (attualmente in $A$) con l'oggetto in posizione $H$ così che al prossimo superscambio $h$ e $k$ andranno a posto. L'oggetto che c'era in $H$ finirà in $A$. E si ricomincia ...
Se in $A$, adesso, c'è $a$, ok, altrimenti poniamo ci sia l'oggetto $m$, andremo a vedere cosa c'è in $M$: se c'è $a$, li scambiamo, se invece c'è $n$ andremo a mettere $m$ in $N$ e quello che c'è in $N$ lo spostiamo in $A$ e via così ...
In questo modo complessivamente sono necessari solo due superscambi.

Cordialmente, Alex

[orsoulx]

@Alex:

Sì due superscambi, per quanto sia grande $ n $, sono sufficienti. Non riesco a seguire le giustificazioni del risultato che, se corrette, dovrebbero portare ad un algoritmo per determinare quali scambi effettuare (vi sono, in generale, molte possibilità diverse).

Ciao
B.