chart - subplot title python

Python 3: orden alfabético perfecto

Question

El objetivo del código es encontrar la subcadena alfabética más larga dentro de una cadena.

s = ''xyzbcdezzz''
longest_string = ''''
current_string = ''''
stringcount = 0

for n in range (len(s) - 1):
    if s[n] <= s[n+1]:
        current_string += (s[n]+s[n+1])
        stringcount += 1
        print(''current string:'', stringcount, current_string)


    elif s[n] > s[n+1]:
        if len(current_string) > len(longest_string) :
            longest_string = current_string
            current_string = ''''
            stringcount = 0
            print(''the longest string checked is:'', longest_string, '', count reset'')

if len(current_string) == len(longest_string):
    print (current_string, longest_string)
if len(current_string) > len(longest_string):
    print (current_string)
if len(longest_string) > len(current_string):
    print(longest_string)

Cuando ejecuto este código, da ''abbccd'' como la subcadena más larga, cuando en realidad es ''abcd''. Esto se debe a que comprueba el carácter a, lo compara con el siguiente en la secuencia, y luego agrega a a b dando "ab". Luego verifica b, comparando con c y agrega bc juntos, y luego agrega "bc" a "ab".

Para solucionar esto, he estado intentando hacer que el bucle omita el siguiente carácter si ya está en orden alfabético, y verifique el siguiente aumentando el valor de ''n'' una vez que se cumple la condición, pero esto no parece hacer nada en absoluto

Consejos, consejos, correcciones y duras críticas son bienvenidos.

EDIT: Parece que he engañado a algunos de ustedes, así que me disculpo. Lo que quise decir es que si tengo una cadena, extrae la subcadena más larga posible en orden alfabético. En el caso de xyzbcdezzz, extraerá ''bcdezzz'' porque es la subcadena de orden alfabético más larga posible, no bcde. El problema con mi código actual, es que da bccddeezzzzz. Si pudiera saltar un bucle cuando la primera condición es verdadera, entonces creo que podría funcionar en mi código.

Answer 1

¿Qué le parece usar una base string de base string de los caracteres alfebéticos y verificar si la subcadena está en esta base string luego devolver la subcadena máxima que se encuentra en la cadena de base en función de su longitud?

Esto es un ejemplo:

def get_max_substring(a):
    base = ''abcdefghijklmnopqrstuvwxyz''
    possibilites = (a[k:k+i] for k in range(len(a)) for i in range(k, len(a)))
    sub = (k for k in possibilites if k in base)
    return max(sub, key= lambda x: len(x))

# Tests
a = ''jamabcdaskl''
final = get_max_substring(a)
print(final)

b = ''asdklfjalkdfjabcdefghijklmnopqrstuvwxyzaaabcasdkfjl;kasdf''
test = get_max_substring(b)
print(test)

Salida:

abcd
abcdefghijklmnopqrstuvwxyz

Answer 2

Aquí está mi implementación:

import itertools

def pairwise(iterable):
    # Taken from https://docs.python.org/3.6/library/itertools.html#itertools-recipes
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)


def longest_sorted_substr(s):
    # Split up in pairs
    pairs = pairwise(s)

    all_substrings = []
    curr_substring = []

    for i, pair in enumerate(pairs):
        if ord(pair[0]) <= ord(pair[1]):
            curr_substring.append(s[i])
        else:
            # Start a new substring
            curr_substring.append(s[i])
            all_substrings.append(''''.join(curr_substring))
            curr_substring = []

    # Don''t forget to add the last character and append the substring
    curr_substring.append(s[-1])
    all_substrings.append(''''.join(curr_substring))

    # Sort the substrings according to length and return the first one
    all_substrings.sort(key=lambda x: len(x), 
                        reverse=True)
    return all_substrings[0]

Pruebas (tomadas de la respuesta de @ salparadise):

assert ''abcdefghi'' == longest_sorted_substr(''abcdezdflkjabcdefghiasldfjlkasdfjkaaabb'')
assert ''abcd'' == longest_sorted_substr(''jamabcdaskl'')
assert ''abcde'' == longest_sorted_substr(''aldksfjklasabcdedjfkladabcd'')
assert ''abcdefghijklmnopqrst'' == longest_sorted_substr(''adfadsabcdefghijklmnopqrst'')
assert ''cghijklmnopqrst'' == longest_sorted_substr(''adfadscghijklmnopqrst'')

No he comparado el rendimiento con las otras respuestas propuestas y tengo en cuenta que distingue entre mayúsculas y minúsculas y espera que la cadena esté formada por caracteres.

Si es necesario, primero puede extraer solo las letras de la cadena y convertirlas en minúsculas usando:

import string
s = ''''.join([letter for letter in s.lower() if letter in string.ascii_letters])

Answer 3

Aquí hay una solución simple, eficiente y (IMO) bastante legible, que esquiva el problema de "qué significa realmente el orden alfabético" tomando una función de prueba personalizada como parámetro:

def longest_matching_substring(s, match):
    current_run_length = 1
    longest_run_length = 1
    longest_run_end = 0

    for i in range(1, len(s)):
        if match(s[i-1], s[i]):
            current_run_length += 1
        else:
            current_run_length = 1

        if current_run_length > longest_run_length:
            longest_run_length = current_run_length
            longest_run_end = i

    longest_run_start = longest_run_end - longest_run_length + 1
    return s[longest_run_start:longest_run_end+1]

Puedes usarlo por ejemplo de esta manera:

print(longest_matching_substring(''jamabcdaskl'', lambda a,b: a < b))

que imprimirá " abcd ". Si desea utilizar una comparación que no distinga mayúsculas de minúsculas y / o ignorar los caracteres no alfabéticos por completo, puede hacerlo cambiando la función de prueba, por ejemplo, de esta forma:

def is_alphabetized(a, b):
    return a.lower() < b.lower()

# this prints "eSt"
print(longest_matching_substring(''TeStInG'', is_alphabetized))

Por supuesto, al definir una función de prueba adecuada, también puede utilizar la misma función longest_matching_substring para encontrar la subcadena consecutiva más larga donde los pares de caracteres adyacentes satisfacen cualquier criterio arbitrario (como, por ejemplo, "no contiene una consonante seguida de una vocal" ). E incluso puede usar la misma función para encontrar subsecuencias consecutivas más largas y coincidentes en otros tipos de secuencias como listas y tuplas, no solo en cadenas.

(Sin embargo, esta implementación no funciona para tipos iterables arbitrarios; para manejarlos, tendríamos que memorizar la subcadena coincidente actual y la más larga a medida que iteramos sobre la entrada. Si bien es factible, eso complicaría un poco el código, y también hacer que sea menos eficiente para cadenas ordinarias y otros tipos de secuencia.)

Answer 4

Desde una perspectiva algorítmica, el enfoque más optimizado es usar un árbol de sufijos para encontrar la cadena secundaria más larga en una cadena determinada. (He implementado una versión optimizada del árbol de sufijos en python hace un tiempo. En caso de que esté interesado, puede consultar https://github.com/kasramvd/SuffixTree

Como otra forma de pirateo, puede utilizar el Numpy para encontrar la subcadena más grande con las funciones diff() , where() y split() :

In [52]: s = ''pqsrjamabcdaskl''

In [54]: ''''.join(max(np.split(list(s), np.where((np.diff([ord(i) for i in s]) == 1) == False)[0] + 1), key=len))
Out[54]: ''abcd''

Explicación:

La lógica detrás de este código es encontrar los índices de los caracteres que la diferencia de su valor ascii es 1.

En numpy simplemente podemos hacer eso mediante la función np.diff . Pero como necesita una serie de elementos, podemos usar una lista de comprensión para pasar la lista de valores deseados a la función. Luego, al comparar el resultado con 1, podemos obtener una lista de bool array de la siguiente manera:

In [55]: np.diff([ord(i) for i in s]) == 1           
Out[55]: 
array([ True, False, False, False, False, False, False,  True,  True,
        True, False, False, False,  True], dtype=bool)

Ahora podemos obtener los índices de los elementos falsos usando np.where para pasarlos a la función de split :

In [57]: np.split(list(s), np.where((np.diff([ord(i) for i in s]) == 1) == False)[0] + 1)
Out[57]: 
[array([''p'', ''q''], 
       dtype=''<U1''), array([''s''], 
       dtype=''<U1''), array([''r''], 
       dtype=''<U1''), array([''j''], 
       dtype=''<U1''), array([''a''], 
       dtype=''<U1''), array([''m''], 
       dtype=''<U1''), array([''a'', ''b'', ''c'', ''d''], 
       dtype=''<U1''), array([''a''], 
       dtype=''<U1''), array([''s''], 
       dtype=''<U1''), array([''k'', ''l''], 
       dtype=''<U1'')]

El +1 es en realidad porque np.split se divide de 0 a nuestro primer índice y luego del primer índice al siguiente y etc.

Y al final, podemos obtener la matriz más larga utilizando la función max al pasar la len como la función clave.

También tenga en cuenta que este enfoque le dará la secuencia consecutiva más larga, si solo le importa el orden, puede reemplazar el == 1 por > 0 . Aquí hay un ejemplo:

In [13]: s = ''pqsrjamabcdasklptvxz''

In [14]: ''''.join(max(np.split(list(s), np.where((np.diff([ord(i) for i in s]) > 0) == False)[0] + 1), key=len))
Out[14]: ''klptvxz''

Answer 5

Después de su edición, es más claro cuál fue su pregunta. He modificado su código lo menos posible para mostrarle de dónde proviene el error en su solución.

Aquí está el código:

s = ''xyzbcdezzz''
longest_string = ''''
current_string = ''''

for n in range(len(s)):
    if len(current_string) == 0 or current_string[-1] <= s[n]:
        current_string += s[n]
        print(''current string:'', len(current_string), current_string)
    else:
        if len(current_string) > len(longest_string):
            longest_string = current_string
        current_string = s[n]
        print(''the longest string checked is:'', longest_string, '', count reset'')

if len(current_string) > len(longest_string):
    longest_string = current_string

print(longest_string)

la parte problemática fue tomar 2 caracteres a la vez en

if s[n] <= s[n+1]:
    current_string += (s[n]+s[n+1])

reemplazándolo con

if len(current_string) == 0 or current_string[-1] <= s[n]:
        current_string += s[n]

agregará a la cadena actual exactamente si la adición es válida (la última char current_string[-1] y el wannabe s[n] agregado s[n] están en orden)

La parte elif se simplifica para no marcar s[n] y s[n+1] porque no refleja lo que estamos tratando de hacer: no nos importa si los caracteres no están en orden en toda la cadena s nos importa nuestra cadena actual (esta lógica es captada por la instrucción if anterior y, de lo contrario, se visitará solo si hay un problema)

entonces el cambio aquí es

elif s[n] > s[n+1]:
    if len(current_string) > len(longest_string) :

a

else:
    if len(current_string) > len(longest_string):
        longest_string = current_string
    current_string = s[n]

agregar un nuevo ganador si es necesario y restablecer la cadena actual al carácter que no estaba en orden

El último conjunto de ifs está verificando el caso cuando current_string termina en el último carácter de la s , aunque esto es correcto, sería menos molesto si agrega un cheque después del bucle e imprime solo la cadena más larga

if len(current_string) > len(longest_string):
        longest_string = current_string
print(longest_string)

De esta manera, la salida es la primera cadena válida más larga en todos los casos y no 2 más largas diferentes cuando una de ellas está en la cola de la cadena

Answer 6

Te pellizqué un poco el código, y lo probé. Parece funcionar perfectamente. Todavía soy un aprendiz, no me importan mis errores menores si hay alguno. Agrega tu cadena como s = ''....''

x = ''abcdefghijklmnopqrstuvwxyz''
current_string = ''''
count=0
longest_string = ''''
for p in range(len(s)-1):

    if x.index(s[p+1])-x.index(s[p]) < 0 and count == 0:
       longest_string = s[count]
       p +=1
    elif x.index(s[p+1])-x.index(s[p]) < 0:
       current_string = ''''

    elif x.index(s[p+1])-x.index(s[p]) >= 0:
       current_string += s[p]
       count += 1
       if len (longest_string) < len (current_string + s[p+1]):
           longest_string = current_string + s[p+1]


print(''Longest substring in alphabetical order is:'', longest_string)

Answer 7

Usando la iteración:

import string
alphabet = string.ascii_lowercase
def check_alpha(sut):
    iterate_alpha = iter(alphabet)
    max_longest = ''''
    current_longest = ''''
    compare_against = next(iterate_alpha)
    for l in sut:
        if l == compare_against:
            current_longest += l
            compare_against = next(iterate_alpha, '''')
        else:
            max_longest = max(current_longest, max_longest, key=len)
            iterate_alpha = iter(alphabet)
            current_longest = next((x for x in iterate_alpha if x == l), '''')
            compare_against = next(iterate_alpha, '''')
    return max(current_longest, max_longest, key=len)

In [39]: assert ''abcdefghi'' == check_alpha(''abcdezdflkjabcdefghiasldfjlkasdfjkaaabb'')
In [40]: assert ''abcd'' == check_alpha(''jamabcdaskl'')
In [83]: assert ''abcde'' == check_alpha(''aldksfjklasabcdedjfkladabcd'')
In [89]: assert ''abcdefghijklmnopqrst'' == check_alpha(''adfadsabcdefghijklmnopqrst'')
In [96]: assert ''ghijklmnopqrst'' ==  check_alpha(''adfadscghijklmnopqrst'')

Answer 8

una versión diferente en bucle sobre zip(strg, strg[1:]) para comparar el carácter anterior y el actual en la misma iteración de bucle:

def longest_substring(strg):

    substring = strg[0]
    max_substring = ''''

    for cur, nxt in zip(strg, strg[1:]):

        if ord(nxt) >= ord(cur):
            substring += nxt
            if len(substring) > len(max_substring):
                max_substring = substring
        else:
            substring = nxt

    return max_substring

¡comparar los caracteres con ord esta manera tiene la desventaja de que estos caracteres !"#$%&''()*+,-./0123456789:;=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[/]^_``abcdefghijklmnopqrstuvwxyz{|}~ considerado como ''en orden alfabético''. Es posible que deba modificarlo según sus necesidades ...

Answer 9

TL; DR: el último código después de la edición resuelve el problema

Esta es una variante del problema de subcadena común más largo.

def longestSubstring(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

alphabets = "abcdefghijklmnopqrstuvwxyz"
s = ''jamabcdaskl''

print(''longest substring:'', longestSubstring(s,alphabets))

Créditos a este post para la subrutina.

Editar:

Parece que el código anterior no funciona en todos los casos, así que tuve que rediseñar la función.

def longestAlphaSubstring(str2):
    str1 = "abcdefghijklmnopqrstuvwxyz"
    longest = ""
    for i in range(len(str1)+1):
        if str1[:i] in str2 and len(str1[:i])>len(longest):
            longest = str1[:i]
    return longest

print(longestAlphaSubstring(''jamabcdaskl''))
print(longestAlphaSubstring(''asdklfjalkdfjabcdefghijklmnopqrstuvwxyzaaabcasdkfjl;kasdf''))

Salida:

abcd
abcdefghijklmnopqrstuvwxyz

Esto funciona en el supuesto de que la subcadena siempre debe comenzar con a . Esto recorre todas las subcadenas posibles desde ''a'', ''ab'', ''abc'', ..., hasta la cadena completa de alfabetos y luego almacena la subcadena más larga encontrada en la verificación.

Para completar, aquí está el código que funcionaría para cualquier subcadena común más larga:

def longestSubstring(str1, str2):
    longest = ""
    for j in range(len(str1)):
        for i in range(len(str1)+1):
            if str1[j:i] in str2 and len(str1[j:i])>len(longest):
                longest = str1[j:i]
    return longest

donde una cadena contiene los alfabetos en orden y la otra contiene la cadena de prueba. Tenga en cuenta que esto es O (n ^ 2) en complejidad (no que sea importante para casos pequeños).