Serve un algoritmo per filtrare questo formato di raccolta

2

Mi dispiace che il titolo sia così vago ... Non riesco a pensare a come descriverlo meglio.

Ho una collezione in questo formato:

var myCollection = [{id:"a"}, {id:"b",excludes:["a"]}, {id:"c",excludes:["b"]}];

Quello che voglio dopo aver eseguito il mio algoritmo è vedere questo:

processedCollection = [{id:"a"}, {id:"c",excludes:["b"]});

In alternativa, se "c" non fosse esistito, allora solo "b" sarebbe visibile. Spero che abbia un senso. È inoltre complicato dalla possibilità che qualsiasi elemento nella raccolta possa escludere più altri elementi (quindi perché è un array).

NOTA: NON devo preoccuparmi dei riferimenti circolari, poiché in questo caso è ragionevole aspettarsi che vengano inseriti solo buoni dati nel mio algoritmo.

Ho tentato di costruire una funzione appropriata ma mi sto sbloccando. Avevo pensato di eseguire prima la raccolta e creare un parametro excludedBy su ciascun elemento e di eseguirlo nuovamente, producendo il risultato corretto, ma non è così semplice.

Qualsiasi aiuto sarebbe molto apprezzato. Spero molto che questo sia un problema noto con algoritmi definiti per affrontarlo! Grazie in anticipo!

    
posta Martin 06.03.2015 - 16:30
fonte

1 risposta

2

Lo penserei come un grafico:

Creareun ordinamento topologico ti darebbe un ordine valido per processare i nodi. Nota ci possono essere molti tipi topologici . Se devi preoccuparti di ciò dipende se hai bisogno di una soluzione o tutte le soluzioni.

In questo caso, esiste un solo ordinamento topologico: c, b, a . Si inizia con c , si aggiunge all'output e si rimuovono tutti i figli diretti dal grafico. Il prossimo nodo non rimosso nell'ordinamento è a , che non ha figli, quindi basta aggiungerlo all'output. Nessun nodo rimane nell'ordinamento topografico, quindi hai finito.

    
risposta data 06.03.2015 - 17:42
fonte

Leggi altre domande sui tag