Controllare se una lista è una rotazione di un altro elenco che funziona con i duplicati

Question

Ho questa funzione per determinare se una lista è una rotazione di un altro elenco:

def isRotation(a,b): 
    if len(a) != len(b): 
    return False 

    c=b*2 
    i=0 

    while a[0] != c[i]: 
    i+=1 

    for x in a: 
    if x!= c[i]: 
     return False 
    i+=1 

    return True 

esempio

>>> a = [1,2,3] 
>>> b = [2,3,1] 
>>> isRotation(a, b) 
True 

Come faccio a funzionare con i duplicati? per esempio.

a = [3,1,2,3,4] 
b = [3,4,3,1,2] 

E può essere eseguito nel tempo O(n)?

Answer 1

si può fare in 0(n) tempo e 0(1) spazio utilizzando una versione modificata di un algoritmo di suffissi massima:

Da Jewels of Stringology: ciclico parità di parole

A rotazione una parola u di lunghezza n è una qualsiasi parola della forma u [k + 1 ... n] [l ... k]. Sia w, due parole della stessa lunghezza n. Si dice che siano equivalenti al ciclo se u (i) == w (j) per alcuni i, j.

Se le parole uew sono scritte come cerchi, sono equivalenti ciclici se i cerchi coincidono dopo le rotazioni appropriate.

Esistono diversi algoritmi di tempo lineare per testare l'equivalenza ciclica di due parole. La più semplice consiste nell'applicare qualsiasi algoritmo di corrispondenza delle stringhe per il modello pat = u e text = ww perché le parole u e w sono cicliche = equivalenti se pat si verifica nel testo.

Un altro algoritmo consiste nel trovare i suffissi massimi di uu e ww e controllare se sono identici sui prefissi della dimensione n. Abbiamo scelto questo problema perché esiste un algoritmo più semplice e interessante, che lavora simultaneamente in tempo lineare e spazio costante, il che merita la presentazione.

Algorithm Cyclic-Equivalence(u, w) 
{ checks cyclic equality of u and w of common length n } 
    x := uu; y := ww; 
    i := 0; j := 0; 
    while (i < n) and (j < n) do begin 
     k := 1; 
     while x[i + k] = y[j + k] do k := k + 1; 
     if k > n then return true; 
     if x[i + k]> y[i + k] then i := i + k else j := j + k; 
     { invariant } 
    end; 
    return false; 

che tradotto in pitone diventa:

def cyclic_equiv(u, v): 
    n, i, j = len(u), 0, 0 
    if n != len(v): 
     return False 
    while i < n and j < n: 
     k = 1 
     while k <= n and u[(i + k) % n] == v[(j + k) % n]: 
      k += 1 
     if k > n: 
      return True 
     if u[(i + k) % n] > v[(j + k) % n]: 
      i += k 
     else: 
      j += k 
    return False 

Esecuzione di alcuni esempi:

In [4]: a = [3,1,2,3,4] 
In [5]: b =[3,4,3,1,2] 
In [6]: cyclic_equiv(a,b) 
Out[6]: True  
In [7]: b =[3,4,3,2,1]  
In [8]: cyclic_equiv(a,b) 
Out[8]: False  
In [9]: b =[3,4,3,2]  
In [10]: cyclic_equiv(a,b) 
Out[10]: False 
In [11]: cyclic_equiv([1,2,3],[1,2,3]) 
Out[11]: True 
In [12]: cyclic_equiv([3,1,2],[1,2,3]) 
Out[12]: True 

Un approccio più semplice sarebbe quello di utilizzare un collections.deque per ruotare gli elementi :

def rot(l1,l2): 
    from collections import deque 
    if l1 == l2: 
     return True 
    # if length is different we cannot get a match 
    if len(l2) != len(l1): 
     return False 
    # if any elements are different we cannot get a match 
    if set(l1).difference(l2): 
     return False 
    l2,l1 = deque(l2),deque(l1) 
    for i in range(len(l1)): 
     l2.rotate() # l2.appendleft(d.pop()) 
     if l1 == l2: 
      return True 
    return False 

Answer 2

penso che si potrebbe usare qualcosa di simile:

a1 = [3,4,5,1,2,4,2] 
a2 = [4,5,1,2,4,2,3] 

# Array a2 is rotation of array a1 if it's sublist of a1+a1 
def is_rotation(a1, a2): 
    if len(a1) != len(a2): 
     return False 

    double_array = a1 + a1 

    return check_sublist(double_array, a2) 

def check_sublist(a1, a2): 
    if len(a1) < len(a2): 
     return False 

    j = 0 
    for i in range(len(a1)): 
     if a1[i] == a2[j]: 
       j += 1 
     else: 
       j = 0 

     if j == len(a2): 
       return True 

    return j == len(a2) 

solo buon senso, se stiamo parlando di domande dell'intervista:

• dovremmo ricordare che la soluzione dovrebbe essere facile da codice e da descrivere.
• non cercare di ricordare la soluzione durante l'intervista. È meglio ricordare il principio di base e ri-implementarlo.

Answer 3

Il seguente meta-algoritmo lo risolverà.

• Costruire una concatenazione di a, per esempio, a = [3,1,2,3,4] =>aa = [3,1,2,3,4,3,1,2,3,4].

• Eseguire qualsiasi adattamento di stringa di un algoritmo di corrispondenza delle stringhe, ad esempio Boyer Moore per trovare b in aa.

---

Uno particolarmente facile attuazione, che avrei provare prima, è quello di utilizzare Rabin Karp come algoritmo sottostante. In questo, si dovrebbe

• calcolare il Rabin Fingerprint per b

• calcolare l'impronta digitale Rabin per aa[: len(b)], aa[1: len(b) + 1], ...E confronta le liste solo quando le impronte digitali corrispondono

Nota che

• L'impronta digitale Rabin per una finestra scorrevole può essere calcolato in modo iterativo in modo molto efficiente (letto su di esso nel link Rabin-Karp)

• Se l'elenco è di interi, in realtà hanno un tempo leggermente più facile che per le stringhe, in quanto non è necessario pensare a quello che è il valore di hash numerico di una lettera

-

Answer 4

alternativa (non ho potuto ottenere la soluzione b in aa al lavoro), si puo 'ruotare' la vostra lista e verificare se la lista ruotato è uguale a B:

def is_rotation(a, b): 

    for n in range(len(a)): 
     c = c = a[-n:] + a[:-n] 
     if b == c: 
      return True 

    return False 

credo che questo sarebbe essere O (n) in quanto ha solo un ciclo for. Speranza che aiuta

Answer 5

Questo sembra funzionare.

def func(a,b): 
    if len(a) != len(b): 
     return False 
    elif a == b: 
     return True 

    indices = [i for i, x in enumerate(b) if x == a[0] and i > 0] 

    for i in indices: 
     if a == b[i:] + b[:i]: 
      return True 

    return False 

E questo anche:

def func(a, b): 
    length = len(a) 

    if length != len(b): 
     return False 

    i = 0 
    while i < length: 
     if a[0] == b[i]: 
      j = i 
      for x in a: 
       if x != b[j]: 
        break 
       j = (j + 1) % length 
      return True 
     i += 1 

    return False 

Answer 6

Se si riesce a rappresentare questi come stringhe invece, basta fare:

def cyclically_equivalent(a, b): 
    return len(a) == len(b) and a in 2 * b 

In caso contrario, si dovrebbe ottenere un algoritmo sottolista ricerca, come ad esempio Knuth -Morris-Pratt (Google fornisce alcune implementazioni) e fare

def cyclically_equivalent(a, b): 
    return len(a) == len(b) and sublist_check(a, 2 * b) 

Answer 7

Si potrebbe provare a testare le prestazioni del proprio utilizzando la funzione di rotazione() nella collezione deque:

from collections import deque 

def is_rotation(a, b): 

    if len(a) == len(b): 
     da = deque(a) 
     db = deque(b) 

     for offset in range(len(a)): 
      if da == db: 
       return True 

      da.rotate(1) 

    return False 

In termini di prestazioni, cosa avete bisogno di fare questo calcolo molte volte per piccoli array, o per alcune volte su array molto grandi? Ciò determinerebbe se il test dei casi speciali lo renderebbe più veloce.

Answer 8

Knuth-Morris-Pratt algorithm è un algoritmo di ricerca stringa che viene eseguito in O (n) dove n è la lunghezza di un testo S (presupponendo l'esistenza della tabella T precostruita, che viene eseguita in O (m) dove m è la lunghezza della ricerca stringa). Tutto sommato è O (n + m).

È possibile eseguire un algoritmo di corrispondenza del modello simile ispirato a KMP.

• Concatenate una lista a se stessa, come a+a o b+b - questo è il testo/lista cercato con n elementi 2 *
• costruire la tabella T base d'altra lista (sia esso b o a) - questo è fatto in O (n)
• eseguire l'algoritmo KMP ispirato - questo è fatto in O (2 * n) (perché si concatena una lista a se stesso)

complessità temporale complessiva è O (2 * n + n) = O (3 * n) che è in O (n)