algorithm - todas - Comprobando si dos cadenas son permutaciones entre sí en Python
permutaciones python 3 (19)
Estoy comprobando si dos cadenas a y b son permutaciones entre sí, y me pregunto cuál es la forma ideal de hacerlo en Python. Desde el Zen de Python, "debe haber una, y preferiblemente solo una, forma obvia de hacerlo", pero veo que hay al menos dos formas:
sorted(a) == sorted(b)
y
all(a.count(char) == b.count(char) for char in a)
pero el primero es más lento cuando (por ejemplo) el primer carácter de a está en ninguna parte en b , y el segundo es más lento cuando en realidad son permutaciones.
¿Hay alguna forma mejor (ya sea en el sentido de más Pythonic, o en el sentido de más rápido en promedio) para hacerlo? ¿O debería simplemente elegir entre estos dos dependiendo de qué situación espero ser más común?
"pero el primero es más lento cuando (por ejemplo) el primer carácter de a está en ninguna parte en b".
Este tipo de análisis de desempeño de casos degenerados no es una buena idea. Es un agujero de rata del tiempo perdido pensando todo tipo de casos especiales oscuros.
Solo realice el análisis "general" de estilo O.
En general, los géneros son O ( n log ( n )).
El a.count(char) for char in a solución es O ( n 2 ). Cada pase de conteo es un examen completo de la secuencia.
Si un caso especial oscuro resulta ser más rápido o más lento, eso es posiblemente interesante. Pero solo importa cuando conoces la frecuencia de tus oscuros casos especiales. Al analizar los algoritmos de ordenamiento, es importante tener en cuenta que un buen número de tipos involucran datos que ya están en el orden correcto (ya sea por suerte o por un diseño inteligente), por lo que se debe ordenar el rendimiento en asuntos de datos previamente ordenados.
En su oscuro caso especial ("el primer carácter de a está en ninguna parte en b") ¿es esto lo suficientemente frecuente como para importar? Si es solo un caso especial en el que pensaste, déjalo a un lado. Si se trata de un hecho sobre sus datos, entonces considérelo.
Creo que el primero es la forma "obvia". Es más corto, más claro y es probable que sea más rápido en muchos casos porque el género incorporado de Python está altamente optimizado.
Tu segundo ejemplo en realidad no funcionará:
all(a.count(char) == b.count(char) for char in a)
solo funcionará si b no contiene caracteres adicionales que no estén en a. También duplica el trabajo si los caracteres en la cadena se repiten.
Si desea saber si dos cadenas son permutaciones de los mismos caracteres únicos , simplemente haga lo siguiente:
set(a) == set(b)
Para corregir tu segundo ejemplo:
all(str1.count(char) == str2.count(char) for char in set(a) | set(b))
los objetos set () sobrecargan el operador OR bit a bit para que evalúe la unión de ambos conjuntos. Esto asegurará que recorra todos los caracteres de ambas cadenas una sola vez por cada carácter.
Dicho esto, el método sorted () es mucho más simple e intuitivo, y sería lo que usaría.
Vaya con el primero, es mucho más sencillo y fácil de entender. Si en realidad se trata de cadenas increíblemente grandes y el rendimiento es un problema real, entonces no use Python, use algo como C.
En lo que se refiere al Zen de Python, que solo debería haber una forma obvia de hacer las cosas, se refiere a cosas pequeñas y simples. Obviamente, para cualquier tarea suficientemente complicada, siempre habrá tropecientos de pequeñas variaciones en las formas de hacerlo.
heurísticamente, es probable que sea mejor dividirlos según el tamaño de la cuerda.
Pseudocódigo:
returnvalue = false
if len(a) == len(b)
if len(a) < threshold
returnvalue = (sorted(a) == sorted(b))
else
returnvalue = naminsmethod(a, b)
return returnvalue
Si el rendimiento es crítico, y el tamaño de la cadena puede ser grande o pequeño, esto es lo que haría.
Es bastante común dividir este tipo de cosas en función del tamaño o tipo de entrada. Los algoritmos tienen diferentes fortalezas o debilidades y sería absurdo usar uno donde otro sería mejor ... En este caso, el método de Namin es O (n), pero tiene un factor constante mayor que el método ordenado O (n log n).
Aquí hay una manera que es O (n), asintóticamente mejor que las dos formas que sugiere.
import collections
def same_permutation(a, b):
d = collections.defaultdict(int)
for x in a:
d[x] += 1
for x in b:
d[x] -= 1
return not any(d.itervalues())
## same_permutation([1,2,3],[2,3,1])
#. True
## same_permutation([1,2,3],[2,3,1,1])
#. False
Esta es una función PHP que escribí hace una semana y que verifica si dos palabras son anagramas. ¿Cómo se compararía esto (si se implementa de la misma manera en python) con los otros métodos sugeridos? ¿Comentarios?
public function is_anagram($word1, $word2) {
$letters1 = str_split($word1);
$letters2 = str_split($word2);
if (count($letters1) == count($letters2)) {
foreach ($letters1 as $letter) {
$index = array_search($letter, $letters2);
if ($index !== false) {
unset($letters2[$index]);
}
else { return false; }
}
return true;
}
return false;
}
Aquí hay una traducción literal a Python de la versión de PHP (por JFS):
def is_anagram(word1, word2):
letters2 = list(word2)
if len(word1) == len(word2):
for letter in word1:
try:
del letters2[letters2.index(letter)]
except ValueError:
return False
return True
return False
Comentarios:
1. The algorithm is O(N**2). Compare it to @namin''s version (it is O(N)). 2. The multiple returns in the function look horrible.
Esta versión es más rápida que cualquier ejemplo presentado hasta ahora, excepto que es 20% más lenta que sorted(x) == sorted(y) para cadenas cortas. Depende de los casos de uso, pero generalmente el 20% de ganancia de rendimiento no es suficiente para justificar una complicación del código al usar versiones diferentes para cadenas cortas y largas (como en la respuesta de @patros).
No usa len por lo que acepta cualquier iterable, por lo tanto, funciona incluso para datos que no caben en la memoria, por ejemplo, dado dos grandes archivos de texto con muchas líneas repetidas, responde si los archivos tienen las mismas líneas (las líneas pueden estar en cualquier orden )
def isanagram(iterable1, iterable2):
d = {}
get = d.get
for c in iterable1:
d[c] = get(c, 0) + 1
try:
for c in iterable2:
d[c] -= 1
return not any(d.itervalues())
except KeyError:
return False
No está claro por qué esta versión es más rápida que defaultdict (@ namin''s) una para iterable1 grande (probada en 25MB tesauro).
Si reemplazamos get in the loop por try: ... except KeyError entonces se realiza 2 veces más lento para cadenas cortas, es decir, cuando hay pocos duplicados.
Aquí está el código martinus en python. Solo funciona para cadenas ASCII:
def is_permutation(a, b):
if len(a) != len(b):
return False
char_count = [0] * 256
for c in a:
char_count[ord(c)] += 1
for c in b:
char_count[ord(c)] -= 1
if char_count[ord(c)] < 0:
return False
return True
Lamento que mi código no esté en Python, nunca lo he usado, pero estoy seguro de que esto se puede traducir fácilmente a python. Creo que esto es más rápido que todos los demás ejemplos ya publicados. También es O (n), pero se detiene lo antes posible:
public boolean isPermutation(String a, String b) {
if (a.length() != b.length()) {
return false;
}
int[] charCount = new int[256];
for (int i = 0; i < a.length(); ++i) {
++charCount[a.charAt(i)];
}
for (int i = 0; i < b.length(); ++i) {
if (--charCount[b.charAt(i)] < 0) {
return false;
}
}
return true;
}
Primero no uso un diccionario sino una matriz de tamaño 256 para todos los caracteres. El acceso al índice debe ser mucho más rápido. Luego, cuando se repite la segunda cadena, inmediatamente devuelvo falso cuando el conteo llega a estar por debajo de 0. Cuando el segundo ciclo ha finalizado, puede estar seguro de que las cadenas son una permutación, porque las cadenas tienen la misma longitud y ningún carácter se usó con mayor frecuencia en b en comparación con a.
Hice una comparación bastante minuciosa en Java con todas las palabras en un libro que tenía. El método de conteo supera al método de clasificación en todos los sentidos. Los resultados:
Testing against 9227 words.
Permutation testing by sorting ... done. 18.582 s
Permutation testing by counting ... done. 14.949 s
Si alguien quiere el algoritmo y el conjunto de datos de prueba, coméntelo.
En Python 3.1 / 2.7 puedes simplemente usar collections.Counter(a) == collections.Counter(b) .
Pero sorted(a) == sorted(b) sigue siendo el más obvio de mi humilde opinión. Está hablando de permutaciones, cambiar el orden, por lo que clasificar es la operación obvia para borrar esa diferencia.
Aquí hay algunas ejecuciones cronometradas en cadenas muy pequeñas, usando dos métodos diferentes:
1. clasificación
2. conteo (específicamente el método original por @namin).
a, b, c = ''confused'', ''unfocused'', ''foncused''
sort_method = lambda x,y: sorted(x) == sorted(y)
def count_method(a, b):
d = {}
for x in a:
d[x] = d.get(x, 0) + 1
for x in b:
d[x] = d.get(x, 0) - 1
for v in d.itervalues():
if v != 0:
return False
return True
Los tiempos de ejecución promedio de los 2 métodos sobre 100.000 bucles son:
no coincidencia (cadena ayb)
$ python -m timeit -s ''import temp'' ''temp.sort_method(temp.a, temp.b)''
100000 loops, best of 3: 9.72 usec per loop
$ python -m timeit -s ''import temp'' ''temp.count_method(temp.a, temp.b)''
10000 loops, best of 3: 28.1 usec per loop
partido (cadena ayc)
$ python -m timeit -s ''import temp'' ''temp.sort_method(temp.a, temp.c)''
100000 loops, best of 3: 9.47 usec per loop
$ python -m timeit -s ''import temp'' ''temp.count_method(temp.a, temp.c)''
100000 loops, best of 3: 24.6 usec per loop
Tenga en cuenta que las cadenas utilizadas son muy pequeñas. La complejidad del tiempo de los métodos es diferente, por lo que verá resultados diferentes con cadenas muy grandes. Elija según sus datos, incluso puede usar una combinación de los dos.
En Swift (u otra implementación de idiomas), puede ver los valores codificados (en este caso, Unicode) y ver si coinciden.
Algo como:
let string1EncodedValues = "Hello".unicodeScalars.map() {
//each encoded value
$0
//Now add the values
}.reduce(0){ total, value in
total + value.value
}
let string2EncodedValues = "oellH".unicodeScalars.map() {
$0
}.reduce(0) { total, value in
total + value.value
}
let equalStrings = string1EncodedValues == string2EncodedValues ? true : false
Necesitará manejar espacios y casos según sea necesario.
def matchPermutation(s1, s2):
a = []
b = []
if len(s1) != len(s2):
print ''length should be the same''
return
for i in range(len(s1)):
a.append(s1[i])
for i in range(len(s2)):
b.append(s2[i])
if set(a) == set(b):
print ''Permutation of each other''
else:
print ''Not a permutation of each other''
return
#matchPermutaion(''rav'', ''var'') #returns True
matchPermutaion(''rav'', ''abc'') #returns False
Esta es una solución O(n) en Python que usa hashing con diccionarios. Tenga en cuenta que no uso diccionarios predeterminados porque el código puede detenerse de esta manera si determinamos que las dos cadenas no son permutaciones después de verificar la segunda letra, por ejemplo.
def if_two_words_are_permutations(s1, s2):
if len(s1) != len(s2):
return False
dic = {}
for ch in s1:
if ch in dic.keys():
dic[ch] += 1
else:
dic[ch] = 1
for ch in s2:
if not ch in dic.keys():
return False
elif dic[ch] == 0:
return False
else:
dic[ch] -= 1
return True
Esto se deriva de la respuesta de @patros .
from collections import Counter
def is_anagram(a, b, threshold=1000000):
"""Returns true if one sequence is a permutation of the other.
Ignores whitespace and character case.
Compares sorted sequences if the length is below the threshold,
otherwise compares dictionaries that contain the frequency of the
elements.
"""
a, b = a.strip().lower(), b.strip().lower()
length_a, length_b = len(a), len(b)
if length_a != length_b:
return False
if length_a < threshold:
return sorted(a) == sorted(b)
return Counter(a) == Counter(b) # Or use @namin''s method if you don''t want to create two dictionaries and don''t mind the extra typing.
Comprobando si dos cadenas son permutaciones entre sí en Python
# First method
def permutation(s1,s2):
if len(s1) != len(s2):return False;
return '' ''.join(sorted(s1)) == '' ''.join(sorted(s2))
# second method
def permutation1(s1,s2):
if len(s1) != len(s2):return False;
array = [0]*128;
for c in s1:
array[ord(c)] +=1
for c in s2:
array[ord(c)] -=1
if (array[ord(c)]) < 0:
return False
return True
Primero, para resolver tales problemas, por ejemplo, si String 1 y String 2 son exactamente iguales o no, fácilmente, puede usar un "si" ya que es O (1). En segundo lugar, es importante considerar que sean valores numéricos o que también sean palabras en la cadena. Si el último es verdadero (las palabras y los valores numéricos están en la cadena al mismo tiempo), su primera solución no funcionará. Puede mejorarlo utilizando la función "ord ()" para convertirlo en valor numérico ASCII. Sin embargo, al final, estás usando sort; por lo tanto, en el peor de los casos, su complejidad de tiempo será O (NlogN). Esta vez la complejidad no está mal. Pero, puedes hacerlo mejor. Puedes hacerlo O (N). Mi "sugerencia" es usar Array (lista) y configurar al mismo tiempo. Tenga en cuenta que encontrar un valor en Array necesita iteración por lo que la complejidad es O (N), pero buscar un valor en el conjunto (que supongo que está implementado con HashTable en Python, no estoy seguro) tiene O (1) complejidad de tiempo :
def Permutation2(Str1, Str2):
ArrStr1 = list(Str1) #convert Str1 to array
SetStr2 = set(Str2) #convert Str2 to set
ArrExtra = []
if len(Str1) != len(Str2): #check their length
return False
elif Str1 == Str2: #check their values
return True
for x in xrange(len(ArrStr1)):
ArrExtra.append(ArrStr1[x])
for x in xrange(len(ArrExtra)): #of course len(ArrExtra) == len(ArrStr1) ==len(ArrStr2)
if ArrExtra[x] in SetStr2: #checking in set is O(1)
continue
else:
return False
return True