python - array - Compruebe si una lista es una rotación de otra lista que funciona con duplicados

python complexity order

Question

Tengo esta función para determinar si una lista es una rotación de otra lista:

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

p.ej

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

¿Cómo hago este trabajo con duplicados? p.ej

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

¿Y puede hacerse en tiempo O(n) ?

Answer 1

Alternativamente (no pude hacer que b in aa solución funcione), puede "rotar" su lista y verificar si la lista rotada es igual 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

Creo que esto sería O (n) ya que solo tiene uno for bucle. Espero eso ayude

Answer 2

Creo que podrías usar algo como esto:

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)

Sólo sentido común si estamos hablando de preguntas de la entrevista:

• debemos recordar que la solución debe ser fácil de codificar y describir.
• No trate de recordar la solución en la entrevista. Es mejor recordar el principio básico y volver a implementarlo.

Answer 3

El siguiente meta-algoritmo lo resolverá.

• Construya una concatenación de a , por ejemplo, a = [3,1,2,3,4] => aa = [3,1,2,3,4,3,1,2,3,4] .

• Ejecute cualquier adaptación de cadena de un algoritmo de coincidencia de cadena, por ejemplo, Boyer Moore para encontrar b en aa .

Una implementación particularmente fácil, que primero intentaría, es usar Rabin Karp como el algoritmo subyacente. En esto, tu

• calcular la huella digital de Rabin para b

• calcule la huella digital de Rabin para aa[: len(b)] , aa[1: len(b) + 1] , ..., y compare las listas solo cuando las huellas digitales coincidan

Tenga en cuenta que

• La huella digital de Rabin para una ventana deslizante se puede calcular de manera iterativamente muy eficiente (lea sobre esto en el enlace Rabin-Karp)

• Si su lista es de enteros, en realidad tiene un tiempo un poco más fácil que para las cadenas, ya que no necesita pensar cuál es el valor de hash numérico de una letra

-

Answer 4

Esto parece funcionar.

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

Y esto también:

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 5

Puede hacerlo en 0(n) tiempo y 0(1) espacio usando una versión modificada de un algoritmo de sufijos máximos:

De las joyas de la estringología : igualdad cíclica de las palabras.

Una rotación de una palabra u de longitud n es cualquier palabra de la forma u [k + 1 ... n] [l ... k]. Sea u, w sean dos palabras de la misma longitud n. Se dice que son cíclicos equivalentes si u (i) == w (j) para algunos i, j.

Si las palabras u y w están escritas como círculos, son cíclicas equivalentes si los círculos coinciden después de las rotaciones apropiadas.

Hay varios algoritmos de tiempo lineal para probar la equivalencia cíclica de dos palabras. El más simple es aplicar cualquier algoritmo de coincidencia de cadenas a los patrones pat = u y text = ww porque las palabras u y w son cíclicas = equivalentes si se produce pat en el texto.

Otro algoritmo es encontrar los sufijos máximos de uu y ww y verificar si son idénticos en los prefijos de tamaño n. Hemos elegido este problema porque hay un algoritmo interesante más simple, que trabaja en tiempo lineal y espacio constante simultáneamente, lo que merece una presentación.

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; 

Lo que traducido a python se convierte en:

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

Ejecutando algunos ejemplos:

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 enfoque más ingenuo sería utilizar colecciones. Para rotar los elementos:

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 6

Puede intentar probar el rendimiento de solo usar la función rotate () en la colección 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

En términos de rendimiento, ¿necesita realizar este cálculo muchas veces para matrices pequeñas o pocas veces en matrices muy grandes? Esto determinaría si las pruebas de casos especiales lo acelerarían o no.

Answer 7

Si puedes representar estos como cadenas, haz lo siguiente:

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

De lo contrario, uno debería obtener un algoritmo de búsqueda sublista, como Knuth-Morris-Pratt (Google da algunas implementaciones) y hacer

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

Answer 8

El algoritmo Knuth-Morris-Pratt es un algoritmo de búsqueda de cadenas que se ejecuta en O (n) donde n es la longitud de un texto S (asumiendo la existencia de la tabla T preconstruida, que se ejecuta en O (m) donde m es la longitud de la cadena de búsqueda). En general, es O (n + m).

Podría hacer un algoritmo de coincidencia de patrones similar inspirado en KMP.

• Concatene una lista a sí misma, como a+a o b+b - este es el texto / lista buscado con 2 * n elementos
• Construya la tabla T en base a la otra lista (ya sea b o a ) - esto se hace en O (n)
• Ejecute el algoritmo inspirado en KMP, esto se hace en O (2 * n) (porque usted concatena una lista para sí mismo)

La complejidad global del tiempo es O (2 * n + n) = O (3 * n) que está en O (n)