¿Cómo verificar si dos cadenas son permutaciones entre sí utilizando O (1) espacio adicional?

13

Dadas dos cadenas, ¿cómo puede verificar si son una permutación entre sí utilizando el espacio O (1)? No se permite modificar las cadenas de ninguna manera.
Nota: O (1) espacio en relación con la longitud de la cadena Y el tamaño del alfabeto.

Anónimo
fuente
3
¿Qué piensas? ¿Qué has intentado y dónde te has atascado? ¿Son las cadenas sobre un alfabeto de tamaño constante? ¿Has intentado calcular sus histogramas?
Yuval Filmus
@YuvalFilmus debe ser O (1) espacio tanto para la longitud de la cadena como para el tamaño del alfabeto
Anónimo
Esto parece claramente imposible. Cualquier algoritmo requerirá espacio adicional para almacenar al menos una posición en una cadena o un solo carácter. Ninguna de estas cosas es O (1).
David Schwartz
@DavidSchwartz: ¿cómo? O (1) significa constante, no una bute. No importa qué tan larga sea la cadena, la posición en ella es un número.
Davor
Depende del modelo de la máquina, obviamente no hay problema en los modelos uniformes. En un modelo de costo logarítmico, el almacenamiento del índice es O(log n)para cadenas de longitud n que no es constante por medio de la longitud ni del tamaño del alfabeto. Cuando las cadenas se pueden modificar temporalmente, creo que hay una solución con un mayor alfabeto que es lineal en el tamaño del alfabeto pero constante en la longitud de la cadena en un modelo logarítmico.
kap

Respuestas:

7

El enfoque ingenuo sería construir histogramas de ambas cadenas y verificar si son iguales. Dado que no se nos permite almacenar una estructura de datos de ese tipo (cuyo tamaño sería lineal al tamaño del alfabeto) que podría calcularse en una pasada, necesitamos contar las ocurrencias de cada símbolo posible después de la otra:

function count(letter, string)
    var count := 0
    foreach element in string
        if letter = element
            count++
    return count

function samePermutation(stringA, stringB)
    foreach s in alphabet
        if count(s, stringA) != count(s, stringB)
            return false
    return true

Por supuesto, esto supone que los recuentos y los índices de iterador son enteros de tamaño constante, en lugar de depender de la longitud de las cadenas.

Bergi
fuente
Como optimización, puede repasar una matriz y solo calcular los histogramas de las letras que encuentre. De esta forma, la complejidad se vuelve independiente del tamaño del alfabeto.
Yuval Filmus
Para expandir el comentario de @YuvalFilmus, necesitaría también 1) verificar que las longitudes de las cadenas sean iguales o 2) iterar sobre ambas cadenas de entrada. Necesita uno de estos, ya que es posible que algunas letras en una no estén en la otra. La opción 1 debería tener menos cálculos.
BurnsBA
@YuvalFilmus Quería evitar eso, ya que significaría una complejidad de tiempo cuadrático, esperaría que el alfabeto sea más pequeño que el tamaño promedio de la cadena. Para cadenas pequeñas y un alfabeto ordenado, consideraría calcular el siguiente símbolo presente más pequeño junto con el conteo en el bucle interno, para que uno pueda omitir algunas iteraciones del bucle del alfabeto, con una complejidad de O(n * min(n, |Σ|)). Hm, ahora que lo pienso, suena bastante como la solución "permitido repetir" de tu respuesta, ¿no?
Bergi
countno es O(1)(es decir, puede desbordarse)
reintroduzca el
1
@Eternalcode Nunca dije que countera un int:-) Sí, no funcionaría, pero en Java eso no puede suceder de todos modos
Bergi
12

Denote las matrices por y suponga que son de longitud n .A,Bn

Supongamos primero que los valores en cada matriz son distintos. Aquí hay un algoritmo que usa espacio :O(1)

  1. Calcule los valores mínimos de ambas matrices y verifique que sean idénticas.

  2. Calcule los segundos valores mínimos de ambas matrices y verifique que sean idénticos.

  3. Y así.

Calcular el valor mínimo de una matriz usa claramente el espacio . Dado el k -ésimo elemento más pequeño, podemos encontrar el ( k + 1 ) st elemento más pequeño al encontrar el valor mínimo mayor que el k -ésimo elemento más pequeño (aquí usamos el hecho de que todos los elementos son distintos).O(1)k(k+1)k

Cuando se permite que los elementos se repitan, modificamos el algoritmo de la siguiente manera:

  1. Calcule los valores mínimos de ambas matrices, cuente cuántas veces aparecen cada uno y verifique m A , 1 = m B , 1 y que los recuentos sean idénticos.metroUN,1,metrosi,1metroUN,1=metrosi,1

  2. Calcule los valores mínimos más grandes que m A , 1 , m B , 1 en las dos matrices (respectivamente), y cuente cuántas veces aparecen cada una. Verifique que m A , 2 = m B , 2 y que los recuentos sean idénticos.metroUN,2,metrosi,2metroUN,1,metrosi,1metroUN,2=metrosi,2

  3. Y así.

Yuval Filmus
fuente
1
¿Sería este enfoque ya que parece que la única forma de encontrar el elemento min en el espacio O ( 1 ) y el acceso de solo lectura a la matriz es iterar sobre todos los elementos? O(norte2)O(1)
Ryan
44
Esto requiere un orden en el alfabeto, aunque es fácil cambiar el algoritmo para no requerirlo. Sin embargo, en el caso "tiene duplicados", esto requiere espacio , no O ( 1 ) . Contar toma espacio. O(lgnorte)O(1)
Derek Elkins salió del SE
77
El conteo necesita espacio (logarítmico), pero, según esta definición del uso del espacio, también lo hace iterar sobre la matriz. Por lo tanto, bajo el estricto significado del uso del espacio, no hay forma de hacerlo en el espacio constante.
Daniel Jour
44
@DanielJour, depende del modelo de costo que esté utilizando. Bajo costo uniforme, esto es posible en espacio constante.
Ryan
77
Si solo se le permite un número constante de bits, solo puede manejar alfabetos de tamaño constante (esto se deduce de la teoría de los idiomas regulares).
Yuval Filmus
2

Defina alguna función f (c) que asigne algún carácter c a un número primo único (a = 2, b = 3, c = 5, etc.).

set checksum = 1
set count = 0 <-- this is probably not even necessary, but it's another level of check
for character c in string 1
    checksum = checksum * f(c)
    count = count + 1
for character c in string 2
    checksum = checksum / f(c)
    count = count = 1

permutation = count == 0 and checksum == 1

Simplemente declarar que puede usar una función de mapeo de números primos es un poco manual, y muy probablemente donde surja un problema manteniendo el espacio .O(1)

Alex Stasse
fuente
Con un límite en el alfabeto, debería usar el espacio O ( 1 ) , de lo contrario creo que no sería un espacio constante. Además, si lo calculara en el espacio O ( 1 ) , sería extremadamente ineficiente según los resultados actuales . Aún así, +1 para el enfoque de primalidad. F(C)O(1)O(1)
Ryan
Otro problema del que me di cuenta después de publicar es que la suma de verificación será un número gigantesco para cadenas grandes, en la medida en que podría violar el requisito de espacio O (1). Esto se puede resolver utilizando flotadores y mutliplying por un carácter en una cadena y luego dividiendo en la otra, luego simplemente diciendo que la suma de verificación debe estar cerca de 1. Las cadenas tendrían que ser realmente gigantescas para que el error de coma flotante sea un problema.
Alex Stasse
44
Tales respuestas son la razón por la que debemos tener cuidado con nuestro modelo de cálculo. El modelo habitual que usamos al analizar algoritmos cuenta la memoria en unidades de palabras de máquina , que tienen bits de tamaño . Entonces no puedes hacer el cálculo en enteros. Si cambia a coma flotante, su algoritmo puede fallar incluso cuando las dos cadenas son permutaciones entre sí, y por el contrario no necesariamente dará la respuesta correcta cuando no lo son. O(Iniciar sesiónnorte)
Yuval Filmus
44
Esto no usa espacio constante. Incluso para un alfabeto fijo, el tamaño de la suma de comprobación número entero va a ser bits para entradas de longitud n . Θ(norte)norte
David Richerby
0

Puedes hacer esto es O(nlogn). Ordene las dos cadenas y compárelas índice por índice. Si difieren en alguna parte, no son permutaciones entre sí.

Para una O(n)solución, se podría usar hashing. Esta función de hashing funcionaría, y epara cualquier letra sería su valor ascii. Si los dos hashes de las cadenas difieren, no son permutaciones entre sí.

La función hash en el enlace:

Un candidato potencial podría ser este. Arregle un número entero impar R. Para cada elemento e que desee calcular hash, calcule el factor (R + 2 * e). Luego calcule el producto de todos estos factores. Finalmente divide el producto entre 2 para obtener el hash.

El factor 2 en (R + 2e) garantiza que todos los factores son impares, evitando así que el producto llegue a ser 0. La división por 2 al final es porque el producto siempre será impar, por lo tanto, la división simplemente elimina un bit constante .

Por ejemplo, elijo R = 1779033703. Esta es una elección arbitraria, hacer algunos experimentos debería mostrar si una R dada es buena o mala. Suponga que sus valores son [1, 10, 3, 18]. El producto (calculado usando entradas de 32 bits) es

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311 Por lo tanto, el hash sería

3376724311/2 = 1688362155.

El uso de doble hashing (o para exagerar aún más) cambiando el valor de R los identificaría con éxito como permutaciones con muy alta probabilidad.

En duda
fuente
1
No puede ordenar las cadenas ya que no puede modificarlas. En cuanto al hashing, es un algoritmo aleatorio que podría dar la respuesta incorrecta.
Yuval Filmus
0

Digamos que tiene dos cadenas llamadas syt.

Puede usar heurísticas para asegurarse de que no sean desiguales.

  1. s.length == t.length
  2. suma de caracteres de s == suma de caracteres en t
  3. [lo mismo que en 2. pero con xor en lugar de suma]

Después de esto, puede ejecutar fácilmente un algoritmo para demostrar que las cadenas son iguales.

  1. ordenar una cadena para que sea igual a la otra y comparar (O (n ^ 2))
  2. ordenar ambos y comparar (O (2n log (n))
  3. verifique cada carácter en s si hay las mismas cantidades en ambas cadenas (O (n ^ 2))

Por supuesto, no puede ordenar tan rápido si no se le permite usar espacio adicional. Por lo tanto, no importa qué algoritmo elija: cada algoritmo que necesite se ejecutará en tiempo O (n ^ 2) cuando solo haya espacio O (1) y si la heurística no pudo demostrar que no pueden ser iguales.

MurksVomOrk
fuente
3
" No se permite modificar las cadenas de ninguna manera " .
Bergi
0

En código de estilo C para toda la rutina:

for (int i = 0; i < n; i++) {
   int k = -1;
   next: for (int j = 0; j <= i; j++)
       if (A[j] == A[i]) {
          while (++k < n)
              if (B[k] == A[i])
                  continue next;
          return false; // note at this point j == i
       }
}
return true; 

O en pseudocódigo muy detallado (usando indexación basada en 1)

// our loop invariant is that B contains a permutation of the letters
// in A[1]..A[i-1]
for i=1..n
   if !checkLetters(A, B, i)
      return false
return true

donde la función checkLetters (A, B, i) verifica que si hay M copias de A [i] en A [1] .. A [i], entonces hay al menos M copias de A [i] en B:

checkLetters(A,B,i)
    k = 0 // scan index into B
    for j=1..i
      if A[j] = A[i]
         k = findNextValue(B, k+1, A[i])
         if k > n
            return false
    return true

y la función findNextValue busca en B un valor que comience desde un índice y devuelve el índice donde se encontró (o n + 1 si no se encuentra).

norte2

Motivo
fuente
¿Puedes convertir tu código C a pseudocódigo? Este no es un sitio de programación.
Yuval Filmus
Esto parece otra variante de la respuesta de Bergi (con algunas diferencias intrascendentes).
Yuval Filmus
O(nortemetro)O(norte2)
0

Creo que este es el algoritmo más simple (con O(norte3) hora, norte longitud de cuerdas)

Recorre string1y string2, para cada personaje, comprueba con qué frecuencia se puede encontrar en string1y string2. Si un personaje está más a menudo en una cadena que en la otra, no es una permutación. Si las frecuencias de todos los caracteres son iguales, entonces las cadenas son permutaciones entre sí.

Aquí hay una pieza de pitón para hacer esto preciso

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references string1 
    #  string2, it is not a copy
    for char in string:
      count1=0
      for char1 in string1:
        if  char==char1:
          count1+=1
      count2=0
      for char2 in string2:
        if  char==char2:
          count2+=1
      if count1!=count2:
        print('unbalanced character',char)
        return()
  print ("permutations")
  return()

check_if_permutations(s1,s2)

El programa necesita algunos punteros a cadenas ( string, string1, string2, char, char1, char2) y las variables de tamañoO(Iniciar sesiónnorte)para contar ( count1, count2). Debe verificar si los caracteres son iguales o no, pero no necesita ningún orden en estos caracteres. Tal vez necesita algunas variables para enteros pequeños (por ejemplo, para mantener valores booleanos o para representar la posición de stringin [string1, string2].

Por supuesto, ni siquiera necesita las variables de conteo, pero puede usar punteros.

s1="abcaba"
s2="aadbba"

def check_if_permutations(string1, string2):
  for string in [string1, string2]:
    # string references one of string1 
    # or string2, it is not a copy
    for char in string:
      # p1 and p2 should be views as pointers
      p1=0
      p2=0
      while (p1<len(string1)) and (p2<len(string2)):
        # p1>=len(string1): p1 points to beyond end of string
        while (p1<len(string1)) and (string1[p1]!=char) :
          p1+=1
        while(p2<len(string2)) and (string2[p2]!=char):
          p2+=1
        if (p1<len(string1)) != (p2<len(string2)):
          print('unbalanced character',char)
          return()
        p1+=1
        p2+=1
  print ("permutations")
  return()

check_if_permutations(s1,s2)

Este segundo programa necesita variables similares al primero, excepto que no necesita el O(Iniciar sesión(norte))variables de tamaño para mantener los valores de conteo.

Por lo tanto, en realidad no depende de norte o el tamaño del alfabeto.

milagro173
fuente
Esto es lo mismo que la solución de Bergi a continuación.
Yuval Filmus
@YuvalFilmus No, no itera sobre todo el alfabeto y, por lo tanto, su tiempo de ejecución no depende del tamaño del alfabeto. Solo usa las dos cadenas que deben probarse. También el segundo programa evita contar.
miracle173
@YuvalFilmus Ahora veo que sus y otros comentarios apuntan en la dirección de la forma en que los utilicé en mi programa.
miracle173