Sortendo le stringhe con vincoli "prima" e "dopo"

Question

Sto cercando di risolvere un problema di soddisfazione dei vincoli per un mio progetto che sembra avere una soluzione ben nota, ma non posso per la vita di me sembra trovarlo descritto da nessuna parte.

Ho studiato quale letteratura posso trovare sui CSP e nessuna delle cose generali sembra fare clic. Sento che forse le mie costolette di CS non sono abbastanza all'altezza del compito, quindi sentiti libero di indicarmi un tutorial che mi farà sentire stupido anche per averlo chiesto, se esiste una cosa del genere.

Quello che sto cercando di fare è questo:

Dato un elenco di stringhe uniche, in cui ogni stringa può avere, sia o nessuno dei seguenti vincoli ad esso associati:

• before, che fa riferimento a un'altra stringa nell'elenco e garantisce che questa stringa si verifichi prima di quella nell'ordinamento finale.
• after, che fa anche riferimento a un'altra stringa nell'elenco e garantisce che questa stringa si verifichi dopo quella nell'ordinamento finale.

Ordina le stringhe in un modo che può garantire la soddisfazione di tutti i vincoli.

Qualcosa come questo:

• 'bar', nessun vincolo
• 'foo', prima 'bar'
• 'baz', nessun vincolo
• 'qux', dopo 'baz'
• 'quux' prima di 'baz', dopo 'foo'

Si tradurrà in un tipo finale come questo:

• 'foo'
• 'sbarra'
• 'Quux'
• 'Baz'
• 'qux'

Sebbene non sia un requisito difficile, preferirei che il risultato sia deterministico. Esistono diverse risposte alternative al problema sopra, poiché "Bar" non ha vincoli oltre a essere dopo "foo". Certo, non mi interessa davvero quale Uno torno finché l'algoritmo produce in modo affidabile lo stesso risultato ogni volta.

Non sarei sorpreso di apprendere che tale determinismo è impossibile poiché sembra essere uno dei principali motivi per cui continuo a imbattermi in blocchi, ma finora non sono stato in grado di dimostrare a me stesso che non può essere fatto.

Naturalmente, dovrò anche essere in grado di rilevare serie di vincoli impossibili da soddisfare, come questo:

• 'foo', nessun vincolo
• 'bar', dopo 'foo'
• 'baz', dopo 'bar', prima di 'foo'

In casi come questo non ho bisogno di alcun tipo di risposta. Devo solo rilevarlo in modo da poter lanciare un'eccezione.

Finora potrebbe essere la naturale inclinazione è stata quella di eliminare un algoritmo genetico, ma ovviamente uccide il determinismo e sarebbe dispendioso se esiste una soluzione migliore che mi richiede solo di sapere cosa diavolo sto facendo, lol. Quindi voglio vedere se posso escludere questa possibilità prima di procedere.

Grazie in anticipo!