Ordina array nel numero minimo di spostamenti

Question

È teoricamente possibile ordinare un array negli spostamenti length(array) - length(longestIncreasingSubsequence(array)) spostando solo elementi che non sono già ordinati.

Se l'unica operazione consentita è una mossa sul posto, rimuovendo un elemento dall'indice A e reinserendolo nell'indice B, un elemento alla volta, come si genererebbe le mosse corrette per finire con l'array ordinato? Anche in questo caso, dovrebbero essere necessari spostamenti length(array) - length(longestIncreasingSubsequence(array)).

Ad esempio, ecco un array:

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ] 

Il più lungo crescente sottosequenza è:

[ 1, 2, 4, 6, 7, 10 ] 

Gli indici di tali elementi sono:

[ 0, 3, 4, 5, 8, 9 ] 

Così, gli indici dobbiamo spostarci:

[ 1, 2, 6, 7] 

poiché questi sono gli indici che non sono già in ordine.

Per finire con un array ordinato, gli indici finale di questi 4 elementi sono:

[ 7, 4, 2, 8] 

Quindi, è necessario spostare simultaneamente 1 all'indice 7, indice 2 all'indice 4, index 6 per indicizzare 2 e indice 7 per indice 8. Il problema è che quando un elemento viene spostato, gli altri elementi vengono spostati rendendo le successive operazioni di spostamento non valide. Ho provato a trasformare questi indici, ma finora non ho trovato la lista corretta delle mosse richieste. Qualche idea?

Spero di aver spiegato il problema abbastanza bene. Per favore, fai domande e io chiarirò. Grazie!

Answer 1

Il tuo problema è che le posizioni di origine sono espresse nell'ordine precedente mentre le posizioni di destinazione sono nell'ordine finale. Quando fai 1-> 7, non sai ancora dove 7 è nell'ordine precedente. È necessario apportare modifiche per tutte le mosse.

Le mosse originali sono:

from: [ 1, 2, 6, 7] 
to: [ 7, 4, 2, 8] 

Fase 1

Let prima trasformata di posizioni come se fossimo rimuovendo tutti gli elementi, poi inserendo gli elementi alle nuove posizioni. Per le posizioni from, procedere da sinistra: rimozione a 1 posizione di spostamento (2,6,7) fino a (1,5,6). Rimozione a 1 ancora spostamenti (5,6) fino a (4,5). Rimozione a 5 turni il 5 in basso a 4. Per ogni posizione in from tutte le posizioni successive con un indice maggiore o uguale devono essere decrementate. Otteniamo:

from: [ 1, 1, 4, 4] 

Per i to posizioni, procedono dalla fine: posizione 8 è corretto. Anche la posizione 2 è corretta, ma significa che il precedente (7,4) era effettivamente (6,3) al momento dell'inserimento. Quindi li aggiustiamo. Analogamente, l'inserimento a 3 significa che la posizione precedente 6 era a 5.

Quindi, per l'array to, procediamo dalla fine, per ogni posizione decrementiamo tutte le posizioni precedenti che hanno un indice più grande. L'array to diventa:

to: [ 5, 3, 2, 8] 

Fase 2

Quello che abbiamo è nella posizione appropriata per 4 traslochi seguiti da 4 inserimenti. Ora vogliamo interlacciare le rimozioni e gli inserimenti.

L'inserimento su 5 deve essere eseguito prima degli assorbimenti in (1, 1, 4). 5 è più grande di ognuna di queste, quindi non influenzerà le posizioni (1, 1, 4), ma il 5 è interessato perché le 3 rimozioni sono fatte a sinistra del punto di inserimento. 5 diventa 8.

L'inserimento su 3 deve precedere le traslazioni in (4, 4). Poiché 3 è più piccolo dei 4, la posizione 3 non è influenzata dalle rimozioni ma le rimozioni devono essere incrementate, in posizioni (5, 5).

L'inserimento a 2 viene prima dell'ultima rimozione a 5 (era 4). E 'più piccolo, quindi il 5 viene regolato a 6.

metodo generale per la fase 2:

for i = 0 to size-1 
    for j = size-1 to i+1 
     if from[j] < to[i] then increment to[i] 
     else increment from[j] 

Dobbiamo ottenere gli array:

from: [ 1, 1, 5, 6] 
to: [ 8, 3, 2, 8] 

Queste sono le mosse finali da eseguire con le posizioni corrette al momento del movimento. Le mosse possono essere lette da sinistra a destra: Rimuovere a 1, inserire a 8. Rimuovere a 1, inserire a 3. Rimuovere a 5, inserire a 2. Rimuovere a 6, inserire a 8.