(In questa risposta, sostituirò "rope" con "string". Userò il termine inventato "xfix" per indicare "un prefisso o un suffisso".)
Esiste naturalmente una soluzione di forza bruta in cui definiamo un ordinamento arbitrario tra le stringhe e quindi scriviamo una semplice ricerca su tutte le possibili combinazioni di parti di stringa. Il problema è che un'implementazione ingenua opera in O ((2 · l) n ) , dove l è la lunghezza media di un stringa. Con la tua grandezza per n , questo non è fattibile sebbene la memoizzazione possa rendere il dolore sopportabile: il problema può essere definito in modo ricorsivo, con una serie di colori mancanti e un elenco di stringhe disponibili passate a ciascuna chiamata. Poiché lo stesso input verrà specificato molto spesso nell'albero di ricerca, la risposta ottimale può essere memorizzata nella cache.
def optimal_combination(strings, colors):
string = strings[0]
remaining_strings = strings[1, ...]
solution = None
foreach xfix in string:
remaining_colors = colors except colors in xfix
possible_solution = xfix + optimal_combination(remaining_strings, remaining_colors)
solution = possible_solution if solution.length < possible_solution.length
return solution
Prima di ricorrere a tali metodi di forza bruta, potremmo voler limitare lo spazio di ricerca. Soprattutto, assumerò che il numero di colori sia molto più piccolo del numero di stringhe. Ora possiamo considerare due soluzioni banali:
- Una corda contiene una xfix che contiene ciascun colore esattamente una volta. Questo xfix è quindi la soluzione.
- Ogni colore si verifica alla fine di una stringa, in modo che la soluzione sia una sequenza di sottostringhe di lunghezza 1.
- ... e tutte le varianti intermedie, ovvero la soluzione è composta da sottostringhe che contengono ciascuna esattamente tutti i colori una sola volta.
Tuttavia può accadere che una tale soluzione di lunghezza minima non sia possibile e che un colore debba verificarsi ripetutamente nell'output. Possiamo semplificare la ricerca scegliendo una struttura dati appropriata. Per ogni xfix, possiamo registrare le seguenti metriche:
- la sua lunghezza
- il set di colori contenuto nella xfix
- quale stringa apparteneva originariamente a
Ora possiamo eseguire iterazioni su tutti i xfix e creare una struttura dati che mappa set di colori sul xfix più corto che contiene tutti questi colori. Questa operazione richiede solo O a = O (2 · l · n) .
color_map = dict()
foreach string in strings:
foreach xfix in string:
colors = colors in xfix
if color_map[colors].xfix.length > xfix.length:
color_map[colors] = {
xfix: xfix,
string: string,
}
A questo punto, potrebbe essere ancora possibile assemblare una stringa più corta per un determinato set di colori. Rimuoviamo questa possibilità iterando attraverso tutte le voci. Una voce può già essere ottimale (se la lunghezza è uguale alla dimensione del set di colori o se è stata assemblata). Altrimenti, se non è ottimale, proviamo a assemblare una stringa più piccola dai set di colori più piccoli, ottimizzandoli anche se necessario (i set di colori di dimensione 1 sono sempre ottimali). Quando si combinano due xfix, occorre fare attenzione che non provengano dalla stessa stringa (ma si noti che non verranno mai combinati due prefissi o due suffissi della stessa stringa, poiché i loro set di colori si sovrappongono). Potrebbe essere opportuno ordinare le voci prima dell'iterazione, garantendo così che tutti i set di colori più piccoli siano già ottimali quando vengono utilizzati in una combinazione. Quando la struttura dati contiene voci m (con m < = 2 · l · n ), l'ordinamento richiede meno di O b = O (m · log m) . Non sono sicuro della classe di complessità di questa operazione di combinazione, in quanto non sono sicuro dell'algoritmo esatto necessario per combinare voci più piccole con quelle di un determinato set di colori.
Problema irrisolto: non sono del tutto sicuro di come assicurarsi che nessun suffisso e postino della stessa stringa possa essere usato insieme - questo potrebbe richiedere il tracciamento dell'insieme di tutte le stringhe usate in ciascuna voce della struttura dati e vieta di combinare quelli in cui la stringa si sovrappone.
A seconda di come gli xfix sono combinati esattamente, può essere ragionevole mantenere un dizionario di insiemi di insiemi, che mappano i colori a tutti i set di colori che contengono questo colore. Questo potrebbe essere facilmente costruito insieme alla combinazione degli xfix se sono combinati strettamente dal basso verso l'alto.
La struttura dati ora contiene solo xfix ottimali e possiamo assemblare la nostra stringa di destinazione da loro, seguendo le stesse regole della combinazione. Questo potrebbe richiedere un po 'di forzatura bruta, ma la maggior parte del lavoro dovrebbe già essere stato fatto.
Finora, si tratta più di un dump di un'idea che di una risposta ben strutturata. Cercherò di evolvere questi concetti durante il giorno e aggiornerò quando avrò più informazioni.