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''