Python - Explicación algoritmo

 
Vista:
sin imagen de perfil
Val: 21
Ha disminuido su posición en 6 puestos en Python (en relación al último mes)
Gráfica de Python

Explicación algoritmo

Publicado por Toni (35 intervenciones) el 02/04/2019 09:11:05
Hola,

un compañero me ha ayudado con el algoritmo de un programa, pero no lo acabo de entender. El algoritmo a resolver es el siguiente:

Hay que escribir una función (def) donde, dada una cadena s y un número entero k, devuelva las n / k subcadenas, teniendo en cuenta los siguientes requisitos:

- el orden de los caracteres en las subcadenas debe ser el mismo que en la cadena original.

- todos los caracteres de las subcadenas deben aparecer una única vez. Es decir, si un carácter se repite dentro de una subcadena, sólo hay que mostrar la primera aparición.

Por ejemplo, si tenemos:
s = AABCCAADA
k = 3

Tenemos que la longitud de la cadena es 9, con lo que podemos formar 3 subcadenas:

- AAB, que pasaría a ser AB (el carácter A se repite dos veces)
- CCA, que pasaría a ser CA (el carácter C se repite dos veces)
- ADA, que pasaría a ser AD (el carácter A se repite dos veces)

El algoritmo es el siguiente:

def split(s, k):
sub = len(s) // k

result = [''] * k

for i in range(sub):
for j in range(k):
if s[k*i+j] not in result[i]:
result[i] += s[k*i+j]

return result

¿Alguien podría explicarme qué hace cada línea del algoritmo?

Muchas gracias
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
sin imagen de perfil
Val: 427
Bronce
Ha aumentado 1 puesto en Python (en relación al último mes)
Gráfica de Python

Explicación algoritmo

Publicado por Daniel (98 intervenciones) el 02/04/2019 11:00:14
Hola,

Primero, si algo no queda claro el un hilo se pregunta en el mismo, sino la gente que llega al hilo se pierde el contexto.

La primera línea de la función calcula la longitud de la cadena y realiza la división entera de esta por el número k. Así se sabe cuantas subdivisiones de s de longitud k se pueden obtener.

La siguiente línea crea un vector de k registros con una cadena vacía. Al multiplicar un vector por un entero este se replica las veces indicadas. Aunque en este caso debería ser sub para que funcione en un caso más genérico.

Luego hay dos bucles. Uno que va de 0 a al numero de subdivisiones menos 1 y otro que va de 0 al k-1. En el bucle comprueba si la cadena en la posición k*i + j ya esta contenida en la subcadena i de resultados, en caso de que no este se agrega. Puedes comprobar que como j va de 0 a k-1, al finalizar el bucle en j siempre continua con el próximo carácter de la cadena original

Si algún punto no queda claro pregunta en esta misma página. No abras otra pregunta.

Saludos,
Daniel Rodríguez.
Analytics Lane
Python en Analytics Lane
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
sin imagen de perfil
Val: 427
Bronce
Ha aumentado 1 puesto en Python (en relación al último mes)
Gráfica de Python

Explicación algoritmo

Publicado por Daniel (98 intervenciones) el 02/04/2019 11:03:57
Perdona, he visto que habías preguntado en el otro hilo. Pero no había visto la pregunta.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar