Algoritmo per l'allineamento sequenziale ciclico

2

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.

    
posta Stefan Czarnecki 22.05.2013 - 15:45
fonte

1 risposta

1

Per prima cosa, per semplificare il problema, rinumiamo in modo tale che la prima sequenza sia 1..n. Il problema viene quindi ridotto alla ricerca degli offset di spostamento per due sequenze tali che per il maggior numero possibile di numeri entrambi hanno un i in posizione i.

Quindi, crea una mappa associativa che mappa da coppie di offset di spostamento al punteggio. Per ogni numero, aumentare il punteggio per la coppia di offset che darebbe una corrispondenza. Infine, trova il punteggio più alto nella mappa.

Viene eseguito nel tempo lineare previsto se si utilizza una mappa hash.

    
risposta data 22.05.2013 - 20:33
fonte

Leggi altre domande sui tag