Rileva le modifiche degli ordini in una lista

Question

Rileva le modifiche degli ordini in una lista

Naviga le tue risposte

#1 da (5 voti)
#2 da (1 voti)
#3 da (0 voti)

3

Supponiamo che tu abbia un elenco di valori

a
b
c
d
e

L'ordine sulla lista potrebbe essere cambiato.

a
c
d
b
e

Come rileveresti questo cambiamento? Avevamo bisogno di qualcosa di simile quando stavamo costruendo una pagina di cronologia delle revisioni per il nostro strumento di creazione di moduli online . Abbiamo trovato una soluzione rapida e sporca, ma sto cercando una soluzione più elegante per questo. Ecco come appaiono le descrizioni delle revisioni:

Ecco la parte difficile: Gli elementi possono essere rimossi / aggiunti da / a in qualsiasi punto dell'elenco. Pertanto, l'algoritmo dovrebbe essere in grado di ignorare tali modifiche.

algorithms

posta Aytekin 31.01.2014 - 11:03

fonte

3 risposte

Leggi altre domande sui tag algorithms

OOP cosa si intende per comunicazione oggetto-oggetto Come trovare il numero di punti con le stesse distanze minime sulla matrice

score 5 · Answer 1

Ci sono due approcci:

Cerca di trovare un modo per applicare l'algoritmo diff al tuo modello. Ciò diventa più semplice quando c'è una rappresentazione testuale sottostante (ad esempio, sorgente HTML o un'altra DSL).
Non fare in modo che il tuo generatore di moduli emetta stati completi, ma solo emetti differenze che puoi facilmente registrare. Invece di avere gli elenchi prima e dopo , devi registrare l'operazione " sposta il campo da x a y ".

score 1 · Answer 2

Crea un doppio elenco collegato per i record. Nel tuo esempio:

per il primo elenco:

a: {prev: -1, next: b}
b: {prev: a, next: c}
c: {prev: b, next: d}
d: {prev: c, next: e}
e: {prev: d, next: -1}

e per la seconda lista

a: {prev: -1, next: c}
c: {prev: a, next: d}
d: {prev: c, next: b}
b: {prev: d, next: e}
e: {prev: b, next: -1}

Ora, quando confronti entrambi gli elenchi, solo le questioni relative alla modifica degli ordini dovrebbero essere "b", poiché è possibile modificare sia il valore precedente sia quello successivo. Solo i record modificati precedenti o successivi al valore non devono essere presi in considerazione poiché si spostano a causa del cambiamento di ordine di "b"

score 0 · Answer 3

Tratterò questa come una domanda sull'algoritmo. Potrebbe non essere ciò che era inteso.

Passa attraverso il primo elenco, creando una ricerca da key- > index. Nel tuo esempio, a- > 1, b- > 2, c- > 3, d- > 4 e così via.
Passa attraverso il secondo elenco, cercando ogni elemento e confrontando il suo indice con l'indice del suo vicino. Nel tuo caso b- > 2 appare dopo d- > 4, che è fuori uso.

Ciascuno degli elementi fuori ordine in base a questo criterio è uno che è stato spostato. Gli elementi inseriti non hanno indice e gli elementi eliminati non saranno esaminati.