Riorganizzazione dell'algoritmo dei cartoni

Question

Riorganizzazione dell'algoritmo dei cartoni

#1 da (1 voti)

1

Dichiarazione del problema -

L'obiettivo è trovare il numero minimo di swap richiesto nella disposizione dei cartoni per ottenere la disposizione desiderata dei cartoni. Solo i cartoni adiacenti possono essere scambiati.

Ho provato un approccio ad hoc, ma si è dimostrato inefficiente verso il limite superiore dell'intervallo di dati. Qui è per riferimento -

Traversing through the given arrangement of cartons
 if position of carton>than the desired position
  swap back
  go to previous iteration

Quale sarebbe un approccio pragmatico al problema?

Intervallo dati di test - N < = 10 ⁵

Fonte - Documento Q INOI 2009

algorithms

posta 7Aces 25.12.2012 - 22:10

fonte

1 risposta

Leggi altre domande sui tag algorithms

Quale sarà il modo migliore per accedere alle informazioni da un altro oggetto Integrità referenziale in un database in cui le tuple non vengono eliminate fisicamente

score 1 · Answer 1

con solo swap adiacenti sei limitato ad un algoritmo di ordinamento O (n ^ 2), (nel peggiore dei casi un set ordinato in ordine inverso)

e dal momento che devi limitarti a una quantità minima di swap puoi confrontare tutto quanto vuoi

un modo per garantire la minor quantità di swap è scambiare solo 2 cartoni quando sono in ordine inverso

sia l'ordinamento di bolle che l'ordinamento di inserimento lo faranno

il modo per calcolare questo minimo è trovare la posizione desiderata di ciascun cartone (con qualsiasi algoritmo di ordinamento) e prendere la somma dell'importo di ciascun cartone spostato e dividere per 2

nel codice psuedo

sort arr
sum=0
foreach c in arr
   sum+= abs(oldIndexOf(c)-indexOf(c))
return sum/2