sacar - encontrar el elemento que mas se repite en una lista python

¿Cómo puedo saber si una cadena se repite en Python?

Question

Estoy buscando una manera de probar si una cadena dada se repite o no para toda la cadena o no.

Ejemplos:

[
''0045662100456621004566210045662100456621'', # ''00456621''
''0072992700729927007299270072992700729927'', # ''00729927''
''001443001443001443001443001443001443001443'', # ''001443''
''037037037037037037037037037037037037037037037'', # ''037''
''047619047619047619047619047619047619047619'', # ''047619''
''002457002457002457002457002457002457002457'', # ''002457''
''001221001221001221001221001221001221001221'', # ''001221''
''001230012300123001230012300123001230012300123'', # ''00123''
''0013947001394700139470013947001394700139470013947'', # ''0013947''
''001001001001001001001001001001001001001001001001001'', # ''001''
''001406469760900140646976090014064697609'', # ''0014064697609''
]

son cadenas que se repiten, y

[
''004608294930875576036866359447'',
''00469483568075117370892018779342723'',
''004739336492890995260663507109'',
''001508295625942684766214177978883861236802413273'',
''007518796992481203'',
''0071942446043165467625899280575539568345323741'',
''0434782608695652173913'',
''0344827586206896551724137931'',
''002481389578163771712158808933'',
''002932551319648093841642228739'',
''0035587188612099644128113879'',
''003484320557491289198606271777'',
''00115074798619102416570771'',
]

son ejemplos de los que no.

Las secciones repetitivas de las cadenas que me dan pueden ser bastante largas, y las cadenas mismas pueden tener 500 o más caracteres, por lo que recorrer cada personaje tratando de construir un patrón y luego verificar el patrón frente al resto de la cadena parece muy lento. Multiplique eso por potencialmente cientos de cadenas y no puedo ver ninguna solución intuitiva.

He examinado un poco las expresiones regulares y parecen buenas para cuando sabes lo que estás buscando, o al menos la longitud del patrón que estás buscando. Lamentablemente, no sé tampoco.

¿Cómo puedo saber si una cadena se repite y, si es así, cuál es la subsecuencia de repetición más corta?

Answer 1

Aquí hay algunos puntos de referencia para las diversas respuestas a esta pregunta. Hubo algunos resultados sorprendentes, incluido un rendimiento muy diferente dependiendo de la cadena que se está probando.

Algunas funciones se modificaron para funcionar con Python 3 (principalmente reemplazando / con // para garantizar la división de enteros). Si ve algo mal, desea agregar su función o desea agregar otra cadena de prueba, haga ping a @ZeroPiraeus en la sala de chat de Python .

En resumen: hay aproximadamente una diferencia de 50x entre las soluciones de mejor y peor desempeño para el amplio conjunto de datos de ejemplo suministrados por OP aquí (a través de this comentario). share es el claro ganador, superando a todos los demás en alrededor de 5 veces para el gran conjunto de ejemplos.

Un par de respuestas son muy lentas en casos extremadamente grandes de "no coincidencia". De lo contrario, las funciones parecen ser iguales o claros ganadores dependiendo de la prueba.

Estos son los resultados, incluidas las parcelas realizadas con matplotlib y seaborn para mostrar las diferentes distribuciones:

Corpus 1 (ejemplos suministrados - conjunto pequeño)

mean performance:
0.0003 david_zhang
0.0009 zero
0.0013 antti
0.0013 tigerhawk_2
0.0015 carpetpython
0.0029 tigerhawk_1
0.0031 davidism
0.0035 saksham
0.0046 shashank
0.0052 riad
0.0056 piotr
median performance:
0.0003 david_zhang
0.0008 zero
0.0013 antti
0.0013 tigerhawk_2
0.0014 carpetpython
0.0027 tigerhawk_1
0.0031 davidism
0.0038 saksham
0.0044 shashank
0.0054 riad
0.0058 piotr

Corpus 2 (ejemplos suministrados - conjunto grande)

mean performance:
0.0006 david_zhang
0.0036 tigerhawk_2
0.0036 antti
0.0037 zero
0.0039 carpetpython
0.0052 shashank
0.0056 piotr
0.0066 davidism
0.0120 tigerhawk_1
0.0177 riad
0.0283 saksham
median performance:
0.0004 david_zhang
0.0018 zero
0.0022 tigerhawk_2
0.0022 antti
0.0024 carpetpython
0.0043 davidism
0.0049 shashank
0.0055 piotr
0.0061 tigerhawk_1
0.0077 riad
0.0109 saksham

Corpus 3 (casos de borde)

mean performance:
0.0123 shashank
0.0375 david_zhang
0.0376 piotr
0.0394 carpetpython
0.0479 antti
0.0488 tigerhawk_2
0.2269 tigerhawk_1
0.2336 davidism
0.7239 saksham
3.6265 zero
6.0111 riad
median performance:
0.0107 tigerhawk_2
0.0108 antti
0.0109 carpetpython
0.0135 david_zhang
0.0137 tigerhawk_1
0.0150 shashank
0.0229 saksham
0.0255 piotr
0.0721 davidism
0.1080 zero
1.8539 riad

Las pruebas y los resultados en bruto están disponibles here .

Answer 2

Aquí hay una solución concisa que evita expresiones regulares y bucles lentos en Python:

def principal_period(s):
i = (s+s).find(s, 1, -1)
return None if i == -1 else s[:i]

Consulte la respuesta Wiki de la comunidad iniciada por @davidism para obtener resultados de referencia. En resumen,

La solución de David Zhang es el claro ganador, superando a todos los demás en al menos 5 veces para el gran conjunto de ejemplos.

(Las palabras de esa respuesta, no las mías).

Esto se basa en la observación de que una cadena es periódica si y solo si es igual a una rotación no trivial de sí misma. Felicitaciones a @AleksiTorhamo por darnos cuenta de que luego podemos recuperar el período principal del índice de la primera aparición de s en (s+s)[1:-1] , y por informarme de los argumentos opcionales de start y end de la string.find de Python string.find .

Answer 3

Aquí hay una solución directa, sin expresiones regulares.

Para las subcadenas de s comienzan desde el índice cero, de longitudes 1 a len(s) , verifique si esa subcadena, substr es el patrón repetido. Esta comprobación se puede realizar concatenando substr con tiempos de ratio sí mismos, de modo que la longitud de la cadena así formada sea igual a la longitud de s . Por lo tanto, ratio=len(s)/len(substr) .

Regrese cuando se encuentre dicha subcadena. Esto proporcionaría la subcadena más pequeña posible, si existe.

def check_repeat(s):
for i in range(1, len(s)):
substr = s[:i]
ratio = len(s)/len(substr)
if substr * ratio == s:
print ''Repeating on "%s"'' % substr
return
print ''Non repeating''
>>> check_repeat(''254725472547'')
Repeating on "2547"
>>> check_repeat(''abcdeabcdeabcdeabcde'')
Repeating on "abcde"

Answer 4

Aquí hay una solución usando expresiones regulares.

import re
REPEATER = re.compile(r"(.+?)/1+$")
def repeated(s):
match = REPEATER.match(s)
return match.group(1) if match else None

Iterando sobre los ejemplos en la pregunta:

examples = [
''0045662100456621004566210045662100456621'',
''0072992700729927007299270072992700729927'',
''001443001443001443001443001443001443001443'',
''037037037037037037037037037037037037037037037'',
''047619047619047619047619047619047619047619'',
''002457002457002457002457002457002457002457'',
''001221001221001221001221001221001221001221'',
''001230012300123001230012300123001230012300123'',
''0013947001394700139470013947001394700139470013947'',
''001001001001001001001001001001001001001001001001001'',
''001406469760900140646976090014064697609'',
''004608294930875576036866359447'',
''00469483568075117370892018779342723'',
''004739336492890995260663507109'',
''001508295625942684766214177978883861236802413273'',
''007518796992481203'',
''0071942446043165467625899280575539568345323741'',
''0434782608695652173913'',
''0344827586206896551724137931'',
''002481389578163771712158808933'',
''002932551319648093841642228739'',
''0035587188612099644128113879'',
''003484320557491289198606271777'',
''00115074798619102416570771'',
]
for e in examples:
sub = repeated(e)
if sub:
print("%r: %r" % (e, sub))
else:
print("%r does not repeat." % e)

... produce esta salida:

''0045662100456621004566210045662100456621'': ''00456621''
''0072992700729927007299270072992700729927'': ''00729927''
''001443001443001443001443001443001443001443'': ''001443''
''037037037037037037037037037037037037037037037'': ''037''
''047619047619047619047619047619047619047619'': ''047619''
''002457002457002457002457002457002457002457'': ''002457''
''001221001221001221001221001221001221001221'': ''001221''
''001230012300123001230012300123001230012300123'': ''00123''
''0013947001394700139470013947001394700139470013947'': ''0013947''
''001001001001001001001001001001001001001001001001001'': ''001''
''001406469760900140646976090014064697609'': ''0014064697609''
''004608294930875576036866359447'' does not repeat.
''00469483568075117370892018779342723'' does not repeat.
''004739336492890995260663507109'' does not repeat.
''001508295625942684766214177978883861236802413273'' does not repeat.
''007518796992481203'' does not repeat.
''0071942446043165467625899280575539568345323741'' does not repeat.
''0434782608695652173913'' does not repeat.
''0344827586206896551724137931'' does not repeat.
''002481389578163771712158808933'' does not repeat.
''002932551319648093841642228739'' does not repeat.
''0035587188612099644128113879'' does not repeat.
''003484320557491289198606271777'' does not repeat.
''00115074798619102416570771'' does not repeat.

La expresión regular (.+?)/1+$ se divide en tres partes:

1. (.+?) es un grupo coincidente que contiene al menos uno (pero lo menos posible) de cualquier carácter (porque +? no es codicioso ).

2. /1+ comprueba al menos una repetición del grupo coincidente en la primera parte.

3. $ comprueba el final de la cadena, para garantizar que no haya contenido adicional que no se repita después de las subcadenas repetidas (y el uso de re.match() asegura que no haya texto que no se repita antes de las subcadenas repetidas).

En Python 3.4 y posterior, puede soltar $ y usar re.fullmatch() lugar, o (en cualquier Python al menos hasta 2.3) ir hacia el otro lado y usar re.search() con la expresión regular ^(.+?)/1+$ , todo lo cual depende más del gusto personal que cualquier otra cosa.

Answer 5

Comencé con más de ocho soluciones a este problema. Algunos eran bases en expresiones regulares (match, findall, split), algunos de corte y prueba de string, y algunos con métodos de string (find, count, split). Cada uno tenía beneficios en la claridad del código, el tamaño del código, la velocidad y el consumo de memoria. Iba a publicar mi respuesta aquí cuando noté que la velocidad de ejecución se clasificó como importante, así que hice más pruebas y mejoras para llegar a esto:

def repeating(s):
size = len(s)
incr = size % 2 + 1
for n in xrange(1, size//2+1, incr):
if size % n == 0:
if s[:n] * (size//n) == s:
return s[:n]

Esta respuesta parece similar a algunas otras respuestas aquí, pero tiene algunas optimizaciones de velocidad que otros no han usado:

• xrange es un poco más rápido en esta aplicación,
• si una cadena de entrada tiene una longitud impar, no verifique ninguna subcadena de longitud par,
• Al usar s[:n] directamente, evitamos crear una variable en cada ciclo.

Me interesaría ver cómo funciona esto en las pruebas estándar con hardware común. Creo que será muy inferior al excelente algoritmo de David Zhang en la mayoría de las pruebas, pero de lo contrario debería ser bastante rápido.

Este problema me pareció muy intuitivo. Las soluciones que pensé que serían rápidas eran lentas. ¡Las soluciones que parecían lentas fueron rápidas! Parece que la creación de cadenas de Python con el operador de multiplicación y las comparaciones de cadenas están altamente optimizadas.

Answer 6

El problema también puede resolverse en O(n) en el peor de los casos con la función de prefijo.

Tenga en cuenta que puede ser más lento en el caso general (UPD: y es mucho más lento) que otras soluciones que dependen del número de divisores de n , pero generalmente encuentran fallas antes, creo que uno de los casos malos para ellos será aaa....aab , donde hay n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a

Primero que nada necesitas calcular la función de prefijo

def prefix_function(s):
n = len(s)
pi = [0] * n
for i in xrange(1, n):
j = pi[i - 1]
while(j > 0 and s[i] != s[j]):
j = pi[j - 1]
if (s[i] == s[j]):
j += 1
pi[i] = j;
return pi

entonces o no hay respuesta o el período más corto es

k = len(s) - prefix_function(s[-1])

y solo tiene que verificar si k != n and n % k == 0 (si k != n and n % k == 0 respuesta es s[:k] , de lo contrario no hay respuesta

Puede verificar la prueba here (en ruso, pero el traductor en línea probablemente hará el truco)

def riad(s):
n = len(s)
pi = [0] * n
for i in xrange(1, n):
j = pi[i - 1]
while(j > 0 and s[i] != s[j]):
j = pi[j - 1]
if (s[i] == s[j]):
j += 1
pi[i] = j;
k = n - pi[-1]
return s[:k] if (n != k and n % k == 0) else None

Answer 7

En la respuesta de David Zhang, si tenemos algún tipo de búfer circular, esto no funcionará: principal_period(''6210045662100456621004566210045662100456621'') debido al inicio 621 , donde me hubiera gustado escupir: 00456621 .

Ampliando su solución podemos usar lo siguiente:

def principal_period(s):
for j in range(int(len(s)/2)):
idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
if idx != -1:
# Make sure that the first substring is part of pattern
if s[:j] == s[j:][:idx][-j:]:
break
return None if idx == -1 else s[j:][:idx]
principal_period(''6210045662100456621004566210045662100456621'')
>>> ''00456621''

Answer 8

Esta función se ejecuta muy rápidamente (probada y es más de 3 veces más rápida que la solución más rápida aquí en cadenas con más de 100k caracteres y la diferencia aumenta a medida que se repite el patrón). Intenta minimizar la cantidad de comparaciones necesarias para obtener la respuesta:

def repeats(string):
n = len(string)
tried = set([])
best = None
nums = [i for i in xrange(2, int(n**0.5) + 1) if n % i == 0]
nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
for s in nums:
if all(t%s for t in tried):
print ''Trying repeating string of length:'', s
if string[:s]*(n/s)==string:
best = s
else:
tried.add(s)
if best:
return string[:best]

Tenga en cuenta que, por ejemplo, para la cadena de longitud 8 verifica solo un fragmento de tamaño 4 y no tiene que probar más porque el patrón de longitud 1 o 2 daría como resultado la repetición del patrón de longitud 4:

>>> repeats(''12345678'')
Trying repeating string of length: 4
None
# for this one we need only 2 checks
>>> repeats(''1234567812345678'')
Trying repeating string of length: 8
Trying repeating string of length: 4
''12345678''

Answer 9

Esta versión intenta solo aquellas longitudes de secuencia candidatas que son factores de la longitud de la cadena; y usa el operador * para construir una cadena de longitud completa a partir de la secuencia candidata:

def get_shortest_repeat(string):
length = len(string)
for i in range(1, length // 2 + 1):
if length % i: # skip non-factors early
continue
candidate = string[:i]
if string == candidate * (length // i):
return candidate
return None

Gracias a TigerhawkT3 por notar que la length // 2 sin + 1 no coincidiría con el caso abab .

Answer 10

Primero, reduzca a la mitad la cadena siempre que sea un duplicado de "2 partes". Esto reduce el espacio de búsqueda si hay un número par de repeticiones. Luego, trabajando hacia adelante para encontrar la cadena repetitiva más pequeña, verifique si dividir la cadena completa por una subcadena cada vez más grande da como resultado solo valores vacíos. Solo se deben probar subcadenas de hasta length // 2 ya que cualquier cosa que no tenga repeticiones.

def shortest_repeat(orig_value):
if not orig_value:
return None
value = orig_value
while True:
len_half = len(value) // 2
first_half = value[:len_half]
if first_half != value[len_half:]:
break
value = first_half
len_value = len(value)
split = value.split
for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
if not any(split(value[:i])):
return value[:i]
return value if value != orig_value else None

Esto devuelve la coincidencia más corta o Ninguna si no hay coincidencia.

Answer 11

Puede hacer la observación de que para que una cadena se considere repetitiva, su longitud debe ser divisible por la longitud de su secuencia repetida. Dado eso, aquí hay una solución que genera divisores de la longitud de 1 a n / 2 inclusive, divide la cadena original en subcadenas con la longitud de los divisores y prueba la igualdad del conjunto de resultados:

from math import sqrt, floor
def divquot(n):
if n > 1:
yield 1, n
swapped = []
for d in range(2, int(floor(sqrt(n))) + 1):
q, r = divmod(n, d)
if r == 0:
yield d, q
swapped.append((q, d))
while swapped:
yield swapped.pop()
def repeats(s):
n = len(s)
for d, q in divquot(n):
sl = s[0:d]
if sl * q == s:
return sl
return None

EDITAR: en Python 3, el operador / ha cambiado para hacer la división flotante por defecto. Para obtener la división int de Python 2, puede usar el operador // lugar. Gracias a @ TigerhawkT3 por llamar mi atención sobre esto.

El operador // realiza la división de enteros tanto en Python 2 como en Python 3, por lo que he actualizado la respuesta para admitir ambas versiones. La parte donde probamos para ver si todas las subcadenas son iguales ahora es una operación de cortocircuito que usa all y una expresión de generador.

ACTUALIZACIÓN: en respuesta a un cambio en la pregunta original, el código ahora se ha actualizado para devolver la subcadena de repetición más pequeña si existe y None si no es así. @godlygeek ha sugerido usar divmod para reducir el número de iteraciones en el generador de divisors , y el código también se ha actualizado para que coincida con eso. Ahora devuelve todos los divisores positivos de n en orden ascendente, excluyendo n mismo.

Actualización adicional para un alto rendimiento: después de varias pruebas, he llegado a la conclusión de que simplemente probar la igualdad de cadenas tiene el mejor rendimiento de cualquier solución de corte o iteración en Python. Por lo tanto, tomé una hoja del libro de @ TigerhawkT3 y actualicé mi solución. Ahora es más de 6 veces más rápido que antes, notablemente más rápido que la solución de Tigerhawk, pero más lento que el de David.

Answer 12

Solución no regex:

def repeat(string):
for i in range(1, len(string)//2+1):
if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
return string[0:i]

Solución más rápida que no es regex, gracias a @ThatWeirdo (ver comentarios):

def repeat(string):
l = len(string)
for i in range(1, len(string)//2+1):
if l%i: continue
s = string[0:i]
if s*(l//i) == string:
return s

La solución anterior rara vez es más lenta que la original en un pequeño porcentaje, pero generalmente es un poco más rápido, a veces mucho más rápido. Todavía no es más rápido que el davidismo para cadenas más largas, y la solución regex de cero es superior para cadenas cortas. Sale al más rápido (según la prueba de davidismo en github, vea su respuesta) con cadenas de aproximadamente 1000-1500 caracteres. De todos modos, es confiablemente el segundo más rápido (o mejor) en todos los casos que probé. Gracias, ThatWeirdo.

Prueba:

print(repeat(''009009009''))
print(repeat(''254725472547''))
print(repeat(''abcdeabcdeabcdeabcde''))
print(repeat(''abcdefg''))
print(repeat(''09099099909999''))
print(repeat(''02589675192''))

Resultados:

009
2547
abcde
None
None
None

Answer 13

Aquí está el código en python que verifica la repetición de la subcadena en la cadena principal dada por el usuario .

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''''):
print "Invalid string"
exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
strarr=strarr+charlist[i]
splitlist=mainstring.split(strarr)
count = 0
for j in splitlist:
if j =='''':
count+=1
if count == len(splitlist):
break
if count == len(splitlist):
if count == 2:
print "No repeating Sub-String found in string %r"%(mainstring)
else:
print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
print "No repeating Sub-String found in string %r"%(mainstring)

Entrada :

0045662100456621004566210045662100456621

Salida :

Longitud de su cuerda: 40

La subcadena ''00456621'' se repite en la cadena ''0045662100456621004566210045662100456621''

Entrada :

004608294930875576036866359447

Salida :

Longitud de su cuerda: 30

No se han encontrado subcadenas repetidas en la cadena ''004608294930875576036866359447''