Sottotitoli ripetuti contigui più piccoli e più grandi in una sequenza

Per evitare di dover enumerare ogni sequenza, è sufficiente osservare che in ogni sottosequenza ripetuta i primi due elementi di ciascuna occorrenza devono essere uguali. In altre parole, ogni coppia ripetuta potrebbe essere l'inizio di una sottosequenza ripetuta più lunga e ogni numero che non inizia una coppia ripetuta non può.

Quindi nel tuo esempio, le coppie ripetute sono 3,6 e 6,17 . Ognuno di questi potrebbe iniziare una sequenza più lunga e nient'altro potrebbe.

Quindi, inizia con un passaggio guardando ciascuna coppia (N-1) e mantieni tutti quelli che si ripetono. Questo formerà un insieme di cluster di punti di partenza della sequenza.

Quindi, all'interno di ciascun cluster, prendi due sequenze alla volta e confronta quanto si estende la corrispondenza. Ricorda il più breve e il più lungo. Hai la tua risposta.

Nel tuo esempio, prova prima ad estendere 3,6 per ogni ricorrenza. La lunghezza massima è 2. Quindi prova ad estendere 6,17 . La lunghezza massima è 5. Problema risolto.

La struttura dati per la registrazione dei cluster è un interessante punto di progettazione. Probabilmente userò un dizionario digitato sui primi due elementi della sequenza e contenente una lista (o vettore) di punti di partenza (indici nei dati originali).

Questo è uno schema di un algoritmo. Dovrebbe essere sufficiente per fornire un punto di partenza se già comprendi il problema e sei un programmatore ragionevolmente buono. Non sono sicuro di poter fornire molto più aiuto senza effettivamente scrivere il codice.

Hai bisogno di una struttura dati e un modo per manipolarlo.

Una possibilità è un albero. Ogni nodo dell'albero (eccetto la radice) contiene un valore uguale a un numero nella sequenza di input, ma lo stesso valore può (di fatto, di solito sarà) verificarsi in più nodi dell'albero. Ogni nodo contiene anche un elenco di "punti di partenza", che potrebbero essere solo le posizioni relative degli elementi della lista (da 0 a N-1). Per ogni percorso unidirezionale dalla radice a un nodo nell'albero, i valori memorizzati nei nodi sul percorso sono i numeri in una sottosequenza della sequenza di input ei punti di partenza elencati nel nodo di destinazione sono tutte le posizioni nell'input sequenza dove a la copia di tale sottosequenza inizia.

Nel tuo esempio, qui ci sono solo alcuni dei nodi che si sarebbero verificati nell'albero:

() -> (3, (1, 5, 14)) -> (6, (1, 5, 14)) -> (5, (5))

Cioè, () è il nodo radice, uno dei suoi figli è (3, (1,5,14)), e così via. Questi nodi rappresentano il fatto che esiste una sottosequenza di un elemento (3) che inizia alle posizioni 1, 5 e 14; anche la sottosequenza (3,6) inizia nelle posizioni 1, 5 e 14; ma la sottosequenza (3,6,5) si verifica solo nella posizione 5. Ci sono molti altri nodi che non ho mostrato qui, per esempio quelli che rappresentano il fatto che una sottosequenza (3,6,17) inizia dalla posizione 1, e quello (3,6,7) inizia alla posizione 14.

Per fare in modo che questo albero rappresenti tutte le sottosequenze che iniziano in una data posizione nella sequenza di input, inizi in quella posizione e leggi i numeri consecutivi dall'input fino a raggiungere la fine dell'input. Mentre leggi ciascun numero, muovi un gradino lungo l'albero verso un nodo che contiene quel numero (se non esiste tale nodo, lo crei) e aggiungi la posizione iniziale specificata nell'elenco su quel nodo.

L'albero è completo quando lo hai fatto una volta per ogni possibile posizione iniziale nell'elenco. A quel tempo, qualsiasi sottosequenza ripetuta è rappresentata da un nodo la cui lista contiene due o più posizioni iniziali. Il nodo più profondo indica quale è stata la sottosequenza più lunga ripetuta.

Se la sottosequenza più lunga fosse tutto ciò di cui avevi bisogno, sarebbe stato sufficiente mantenere un contatore su ogni nodo anziché su una lista. Ma per la sottosequenza non estendibile più breve, è utile conoscere le posizioni iniziali. Ad esempio, scegli qualsiasi nodo che ti piace nell'albero. Considera la sottosequenza rappresentata da quel nodo. Per determinare che la sottosequenza non può essere estesa verso la fine dell'elenco, verificare che nessuno dei figli del nodo scelto abbia più di un punto iniziale nell'elenco. Per determinare che la sottosequenza non può essere estesa verso l'inizio della lista, guarda i numeri nella sequenza di input immediatamente prima di ognuno dei punti di partenza del tuo nodo scelto e verifica che due di questi numeri non siano uguali. Puoi eseguire una ricerca in larghezza dell'albero e fermarti quando trovi un nodo che supera entrambi i test.

Ma guardando di nuovo l'input, vedo che la sottosequenza (19,3,6) si verifica due volte, quindi forse ho frainteso i tuoi criteri per "sottosequenze ripetute più brevi". Se quello che intendi è che c'è almeno una copia di (3,6), quella che inizia alla posizione 1, che è ripetuta altrove nell'input ma non può essere estesa in avanti o indietro, quindi invece di "no due di quei numeri sono uguali ", il paragrafo precedente dovrebbe dire" c'è almeno un numero che si verifica esattamente una volta ". Cioè, nell'esempio, la sottosequenza (3,6) che inizia alla posizione 1 è preceduta dal valore 1, e questa è l'unica volta che (3,6) è preceduto da 1.

Questo non è sicuramente il modo più veloce per ottenere una risposta, ma è meglio di quanto potrebbero essere alcuni approcci a forza bruta. Ci sono ancora molti dettagli di implementazione da ottimizzare. Potresti essere in grado di ottimizzarlo ulteriormente; per esempio, piuttosto che usare la procedura che ho dato per riempire i nodi dell'albero, forse puoi usare una procedura del tipo delineata da david.pfx, nel qual caso l'albero risultante sarà molto più piccolo (perché non lo fai costruisci molti nodi senza scopo)

Potresti usare gli schemi ... Per trovare la sottosequenza ripetuta più lunga prova questo ...

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {___, Longest[y___], ___, Longest[y___], ___} :> y

Restituisce Sequence [6,17,19,3,6]

Per trovare la sottosequenza ripetitiva non banale (vale a dire la lunghezza 2 o superiore) prova questo ...

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {___, Shortest[y___ /; Length[{y}] >= 2], ___, 
   Shortest[y___], ___} :> y

Questo restituisce Sequence[3,6]

Nota: le risposte vengono restituite come oggetti Sequence. Se, invece, vuoi *** liste *** restituito cambia il y finale che appare dopo il simbolo :> a {y} .

Posso esprimere la stessa soluzione in termini più dettagliati come ...

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {BlankNullSequence[], Longest[y___], BlankNullSequence[], 
   Longest[y___], BlankNullSequence[]} :> y

{1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 
  101} /. {BlankNullSequence[], Shortest[y___ /; Length[{y}] >= 2], 
   BlankNullSequence[], Shortest[y___], BlankNullSequence[]} :> y