Diciamo che abbiamo 3 sequenze cicliche, ognuna di esse di lunghezza n e che contiene ogni numero dell'intervallo 1. Una volta.
L'obiettivo è allineare le sequenze per massimizzare il numero di corrispondenze tra le sequenze. Per corrispondenza intendo una colonna che contiene 3 valori identici. Poiché le sequenze sono cicliche, possiamo spostare ciclicamente ogni sequenza per un numero qualsiasi di posizioni (quindi 1- > 2 > 3 può diventare 2- > 3- > 1 e 3- > 1- > 2 ma non 1- > 3- > 2).
Esempio:
1 5 4 3 2
1 3 2 4 5
2 1 5 4 3
La risposta dovrebbe essere 3 e l'allineamento corrispondente è mostrato sotto (cinque, tre e due sono abbinati).
1 5 4 3 2
4 5 1 3 2
1 5 4 3 2
Un semplice algoritmo quadratico che ho trovato è:
per i in 1..n:
allineare le sequenze in modo che la colonna (i, i, i) sia stata creata
conta il numero di partite
se è maggiore del massimo corrente, imposta un nuovo massimo
Sfortunatamente le sequenze possono avere una lunghezza di 1000000 e quindi il mio approccio non è abbastanza veloce. Gradirei che qualcuno potesse suggerire un algoritmo subquadratico (lineare, loglineare?) Per questo problema.