Trovare un periodo di sequenza eventualmente finale

Question

Breve spiegazione.

Ho una sequenza di numeri [0, 1, 4, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7]. Come vedi, dal valore 3-rd la sequenza è periodica con un periodo [0, 0, 1, 1, 2, 3, 7].

Sto tentando di estrarre automaticamente questo periodo da questa sequenza. Il problema è che né conosco la durata del periodo, né so da quale posizione la sequenza diventa periodica.

completa spiegazione (potrebbe richiedere un po 'di matematica)

sto imparando la teoria dei giochi combinatoria e una pietra miliare di questa teoria richiede uno per calcolare Grundy values di un grafico del gioco. Questo produce una sequenza infinita, che in molti casi diventa eventually periodic.

Ho trovato un modo per calcolare in modo efficiente i valori di grundy (mi restituisce una sequenza). Vorrei estrarre automaticamente l'offset e il periodo di questa sequenza. Sono consapevole che vedendo una parte della sequenza [1, 2, 3, 1, 2, 3] non si può essere certi che [1, 2, 3] sia un punto (chi sa potrebbe essere il prossimo numero è 4, che rompe l'ipotesi), ma non mi interessa la complessità (presumo che la sequenza è sufficiente per trovare il periodo reale). Anche il problema è che la sequenza può fermarsi nel mezzo del periodo: [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, ...] (il periodo è ancora 1, 2, 3).

Devo anche trovare l'offset e il periodo più piccoli. Ad esempio per la sequenza originale, l'offset può essere [0, 1, 4, 0, 0] e il periodo [1, 1, 2, 3, 7, 0, 0], ma il più piccolo è [0, 1, 4] e [0, 0, 1, 1, 2, 3, 7].

---

Il mio approccio inefficace è provare ogni offset possibile e ogni periodo possibile. Costruisci la sequenza usando questi dati e verifica se è uguale all'originale. Non ho fatto nessuna analisi normale, ma sembra che sia almeno quadratico in termini di complessità temporale.

Ecco il mio codice python rapida (non sono testati in modo corretto):

def getPeriod(arr): 
    min_offset, min_period, n = len(arr), len(arr), len(arr) 
    best_offset, best_period = [], [] 
    for offset in xrange(n): 
     start = arr[:offset] 
     for period_len in xrange(1, (n - offset)/2): 
      period = arr[offset: offset+period_len] 
      attempt = (start + period * (n/period_len + 1))[:n] 

      if attempt == arr: 
       if period_len < min_period: 
        best_offset, best_period = start[::], period[::] 
        min_offset, min_period = len(start), period_len 
       elif period_len == min_period and len(start) < min_offset: 
        best_offset, best_period = start[::], period[::] 
        min_offset, min_period = len(start), period_len 

    return best_offset, best_period 

Il che mi riporta quello che voglio per la mia sequenza originale:

offset [0, 1, 4] 
period [0, 0, 1, 1, 2, 3, 7] 

C'è qualcosa di più efficiente?

Answer 1

1. Vorrei iniziare con la costruzione istogramma dei valori nella sequenza

   Quindi basta fare un elenco di tutti i numeri utilizzati in sequenza (o una parte significativa di esso) e contare il loro verificarsi. Questo è O(n) dove n è la dimensione della sequenza.

2. sorta l'istogramma crescente

   Questo è O(m.log(m)) dove m è il numero di valori distinti.È anche possibile ignorare i numeri a basso potenziale (count<treshold) che sono più probabili nell'offset o semplicemente le irregolarità che si abbassano ulteriormente m. Per le sequenze periodiche m <<< n in modo da poterlo utilizzare come primo marcatore se la sequenza è periodica o meno.

3. scoprire il periodo

   Nel istogramma il counts dovrebbe essere intorno multipli del n/period. Approssimativamente/trova GCD dei conteggi degli istogrammi. Il problema è che è necessario tenere conto delle irregolarità presenti nei conteggi e anche nella parte n (parte offset), quindi è necessario calcolare circa GCD. istogramma

   sequence = { 1,1,2,3,3,1,2,3,3,1,2,3,3 } 
   

   ha ordinato:: per esempio

   item,count 
   2 3 
   1 4 
   3 6 
   

   il GCD(6,4)=2 e GCD(6,3)=3 si dovrebbe verificare almeno +/-1 intorno alle GCD risultati in modo che i possibili periodi sono circa:

   T = ~n/2 = 13/2 = 6 
   T = ~n/3 = 13/3 = 4 
   

   Così

   controllare T={3,4,5,6,7} solo per essere sicuro. Utilizzare sempre GCD tra i conteggi più alti e i conteggi più bassi. Se la sequenza ha molti numeri distinti, puoi anche fare un istogramma di conteggi controllando solo i valori più comuni.

   Per verificare la validità del periodo basta prendere qualsiasi oggetto vicino alla fine o al centro della sequenza (utilizzare solo un'area periodica probabile). Poi cercalo in un'area vicina a un probabile periodo prima (o dopo) della sua comparsa. Se trovato poche volte hai il giusto periodo (o suo multiplo)

4. Prendi il periodo esatto

   Basta controllare le frazioni di periodo trovati (T/2, T/3, ...) o fare un istogramma sul periodo trovato e il più piccolo count ti dice quanti periodi reali hai incapsulato quindi dividi per esso.

5. trovare compensato

   Quando si conosce il periodo di questo è facile. Basta scansionare da inizio prendere il primo oggetto e vedere se dopo il periodo è di nuovo lì. Se non ricordi la posizione. Fermati alla fine o nel mezzo della sequenza ... o su alcuni conseguenti successi. Questo è fino a O(n) E l'ultima posizione memorizzata è l'ultimo elemento nello offset.

[edit1] era curioso così provo a codificare in C++

ho semplificato/saltare alcune cose (presupponendo almeno metà dell'array è periodica) per verificare se non fare qualche errore stupido nel mio algoritmo e qui il risultato (Funziona come previsto):

const int p=10;   // min periods for testing 
const int n=500;  // generated sequence size 
int seq[n];    // generated sequence 
int offset,period;  // generated properties 
int i,j,k,e,t0,T; 
int hval[n],hcnt[n],hs; // histogram 

// generate periodic sequence 
Randomize(); 
offset=Random(n/5); 
period=5+Random(n/5); 
for (i=0;i<offset+period;i++) seq[i]=Random(n); 
for (i=offset,j=i+period;j<n;i++,j++) seq[j]=seq[i]; 
if ((offset)&&(seq[offset-1]==seq[offset-1+period])) seq[offset-1]++; 

// compute histogram O(n) on last half of it 
for (hs=0,i=n>>1;i<n;i++) 
    { 
    for (e=seq[i],j=0;j<hs;j++) 
    if (hval[j]==e) { hcnt[j]++; j=-1; break; } 
    if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; } 
    } 
// bubble sort histogram asc O(m^2) 
for (e=1,j=hs;e;j--) 
for (e=0,i=1;i<j;i++) 
    if (hcnt[i-1]>hcnt[i]) 
    { e=hval[i-1]; hval[i-1]=hval[i]; hval[i]=e; 
    e=hcnt[i-1]; hcnt[i-1]=hcnt[i]; hcnt[i]=e; e=1; } 
// test possible periods 
for (j=0;j<hs;j++) 
if ((!j)||(hcnt[j]!=hcnt[j-1])) // distinct counts only 
    if (hcnt[j]>1)     // more then 1 occurence 
    for (T=(n>>1)/(hcnt[j]+1);T<=(n>>1)/(hcnt[j]-1);T++) 
    { 
    for (i=n-1,e=seq[i],i-=T,k=0;(i>=(n>>1))&&(k<p)&&(e==seq[i]);i-=T,k++); 
    if ((k>=p)||(i<n>>1)) { j=hs; break; } 
    } 

// compute histogram O(T) on last multiple of period 
for (hs=0,i=n-T;i<n;i++) 
    { 
    for (e=seq[i],j=0;j<hs;j++) 
    if (hval[j]==e) { hcnt[j]++; j=-1; break; } 
    if (j>=0) { hval[hs]=e; hcnt[hs]=1; hs++; } 
    } 
// least count is the period multiple O(m) 
for (e=hcnt[0],i=0;i<hs;i++) if (e>hcnt[i]) e=hcnt[i]; 
if (e) T/=e; 

// check/handle error 
if (T!=period) 
    { 
    return; 
    } 

// search offset size O(n) 
for (t0=-1,i=0;i<n-T;i++) 
if (seq[i]!=seq[i+T]) t0=i; 
t0++; 

// check/handle error 
if (t0!=offset) 
    { 
    return; 
    } 

Il codice non è ancora ottimizzato. Per n=10000 ci vuole circa 5ms sulla mia configurazione.Il risultato è t0 (offset) e T (periodo). Potrebbe essere necessario giocare con la soglia costanti un po

Answer 2

Nota: Se c'è un periodo P1 di lunghezza L, poi c'è anche un periodo P2, con il stessa lunghezza, L, tale che la sequenza di input termina esattamente con P2 (ie alla fine non è previsto un periodo parziale).

In effetti, un diverso periodo della stessa lunghezza può sempre essere ottenuto modificando l'offset. Il nuovo periodo sarà una rotazione del periodo iniziale.

Ad esempio la seguente sequenza ha un periodo di lunghezza 4 e offset 3:

0 0 0 (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2

ma ha anche un periodo con la stessa lunghezza 4 e sfalsati 5, senza un periodo parziale alla fine :

0 0 0 1 2 (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2) (3 4 1 2)

---

l'implicazione è che possiamo trovare la lunghezza minima di un periodo elaborando la sequenza in ordine inverso e cercando il periodo minimo usando l'offset zero dalla fine. Un possibile approccio è quello di utilizzare semplicemente l'algoritmo corrente nella lista inversa, senza la necessità di eseguire il loop over offset.

Ora che conosciamo la durata del periodo desiderato, possiamo anche trovare il suo offset minimo. Un possibile approccio consiste nel provare tutti i vari offset (con il vantaggio di non aver bisogno delle lunghezze di loop over, poiché la lunghezza è nota), tuttavia, se necessario, sono possibili ulteriori ottimizzazioni, ad es. avanzando il più possibile durante l'elaborazione dell'elenco dalla fine, consentendo la parziale ripetizione del periodo (, ovvero quello più vicino all'inizio della sequenza inversa).

Answer 3

Ho dovuto fare qualcosa di simile una volta. Ho usato la forza bruta e un po 'di buon senso, la soluzione non è molto elegante ma funziona. La soluzione funziona sempre, ma devi impostare i parametri corretti (k, j, con) nella funzione.

• La sequenza viene salvato come un elenco nella variabile seq.
• k è la dimensione della serie di sequenze, se si pensa che la sequenza richiederà molto tempo per diventare periodica, quindi impostare questo k su un numero elevato.
• La variabile trovato ci dirà se la matrice ha superato il test periodico con periodo j
• j è il periodo.
• Se si prevede un periodo enorme, è necessario impostare j su un numero elevato.
• Testiamo la periodicità controllando gli ultimi numeri j + 30 della sequenza.
• Più grande è il periodo (j) più dobbiamo controllare.
• Non appena viene superato uno dei test, si esce dalla funzione e si restituisce il periodo più piccolo.

Come si può notare la precisione dipende dalle variabili j e k ma se si imposta loro di numeri molto grandi sarà sempre corretta.

def some_sequence(s0, a, b, m): 
    try:  
     seq=[s0] 
     snext=s0 
     findseq=True 
     k=0 
     while findseq:  
      snext= (a*snext+b)%m 
      seq.append(snext) 

#UNTIL THIS PART IS JUST TO CREATE THE SEQUENCE (seq) SO IS NOT IMPORTANT 
      k=k+1 
      if k>20000: 
       # I IS OUR LIST INDEX 
       for i in range(1,len(seq)): 
        for j in range(1,1000): 
         found =True 
         for con in range(j+30): 
          #THE TRICK IS TO START FROM BEHIND     
          if not (seq[-i-con]==seq[-i-j-con]): 
           found = False 
         if found: 
          minT=j 
          findseq=False 
          return minT 

except: 

    return None 

versione semplificata

def get_min_period(sequence,max_period,test_numb): 
    seq=sequence 
    if max_period+test_numb > len(sequence): 
     print("max_period+test_numb cannot be bigger than the seq length") 
     return 1 
    for i in range(1,len(seq)):  
     for j in range(1,max_period): 
      found =True 
      for con in range(j+test_numb):          
       if not (seq[-i-con]==seq[-i-j-con]): 
        found = False 
      if found:   
       minT=j 
       return minT 

Dove max_period è il periodo massimo che si desidera cercare, e test_numb è quanti numeri della sequenza che si desidera testare, il più grande è meglio ma devi fare max_period + test_numb < len (sequenza)