Encontrar la secuencia repetida más larga en una lista.

10 Jun, 2023 Programación 0

Si tengo una lista así:

[i;i;i;a;b;b;a;i;i;c]
(La secuencia más larga repetida sería [i;i])
[i;i;i;i]
(Aquí el patrón máximo sería [i;i] (tiene que repetirse, sin superposición))
[t;f;f;t]
(Aquí sería [t] ya que t es, en este caso, el primer elemento que tiene un patrón repetido en la lista)

Mi idea:

Tomar el primer elemento de la lista y dividir la lista, donde la lista uno tiene todos los elementos a la izquierda del primer elemento y la lista dos todos los elementos a la derecha.
Luego, verificar si el elemento tiene una coincidencia en una de las dos listas.
Si tiene una coincidencia, establecer el máximo actual en el elemento.
Ahora, concatenar el siguiente elemento a la derecha del elemento actual en la lista original con el elemento actual y buscar nuevamente en la lista uno y dos si hay una coincidencia.
Después de que la longitud de la concatenación alcance un punto donde es mayor que (tamaño de la lista / 2), detener.
Ahora, ir al primer paso pero con el siguiente elemento y repetir hasta que se verifique cada elemento en la lista.

Ejemplo:

[t;f;f;t]
(primer ronda)
[t][][f;f;t]
(una coincidencia en el último elemento)
current_max = [t]
(segunda ronda)
[t;f][][f;t]
(desde aquí, no hay más coincidencias)
(ir al siguiente elemento, dividir las listas nuevamente y continuar con los pasos mencionados)
[f][t][f;t]
(coincidencia en f) 
(repetir desde aquí...)

No sé si este algoritmo tiene fallas. Estoy intentando implementarlo en OCaml, pero creo que puede haber una manera más fácil de hacerlo.

davy.ai

June 10, 2023 at 2:24 pm

Tu idea de encontrar la secuencia repetida más larga en una lista es un buen comienzo, pero puede que no sea el algoritmo más eficiente o preciso. Aquí hay algunas posibles problemas con tu enfoque:

Dividir la lista en dos partes y buscar coincidencias en cada parte puede que no considere todos los patrones posibles. Podría haber un patrón repetitivo que se extiende por ambas partes, o un patrón más corto que comienza en el medio de la lista. Deberías buscar de forma recursiva patrones en todas las posibles sub-listas.
Concatenar elementos y buscar coincidencias también puede perder algunos patrones. Por ejemplo, en la lista [a;b;a;b;c], tu algoritmo encontraría [a;b], pero la secuencia repetida más larga es realmente [a;b;a;b].
Tu algoritmo también puede tener algunos pasos redundantes. Por ejemplo, una vez que encuentras un patrón coincidente, no necesitas seguir buscando concatenaciones más pequeñas de los mismos elementos.

Un enfoque más robusto sería iterar sobre la lista y mantener un seguimiento del patrón más largo encontrado hasta ahora. Puedes hacer esto manteniendo una ventana deslizante de los últimos n elementos y verificando si esa ventana coincide con alguna ventana anterior en la lista. Aquí hay algún código de muestra:

let rec find_longest_pattern list =
  match list with
  | [] -> []
  | x :: xs ->
    let rec check_window n window rest longest =
      match rest with
      | [] -> longest
      | y :: ys ->
        let next_window = if n >= List.length window then window else List.tl window in
        let new_window = List.append next_window [y] in
        let pattern_length = n + 1 in
        let matching_patterns = List.filter (fun wnd -> wnd = new_window) (List.tl (List.tl (List.rev_list list))) in
        match matching_patterns with
        | [] -> check_window pattern_length new_window ys longest
        | _ -> check_window pattern_length new_window ys new_window
    in
    let longest_pattern = List.fold_left (fun acc x -> if List.length x > List.length acc then x else acc) [] in
    check_window 0 [x] xs longest_pattern

Esta función toma una lista como entrada y devuelve el patrón repetido más largo encontrado. La función check_window verifica de forma recursiva cada ventana de tamaño n en la lista, deslizando la ventana un elemento hacia la derecha y comparándola con todas las ventanas anteriores. Si se encuentra una coincidencia, la función actualiza el patrón más largo encontrado hasta ese momento. Una vez que ha verificado todas las posibles ventanas, devuelve el patrón más largo.

La función find_longest_pattern usa fold_left para aplicar check_window a cada elemento de la lista y devuelve el patrón más largo encontrado. Ten en cuenta que este algoritmo solo considera patrones no superpuestos, por lo que devolvería [i;i] para la lista [i;i;i;i], en lugar de [i;i;i] (lo que puede o no ser deseado).

Este es solo uno de los posibles algoritmos para encontrar el patrón repetido más largo en una lista, y puede haber otros enfoques que sean más eficientes o precisos.

Answer

davy.ai

June 10, 2023 at 2:24 pm
Tu idea de encontrar la secuencia repetida más larga en una lista es un buen comienzo, pero puede que no sea el algoritmo más eficiente o preciso. Aquí hay algunas posibles problemas con tu enfoque:
- Dividir la lista en dos partes y buscar coincidencias en cada parte puede que no considere todos los patrones posibles. Podría haber un patrón repetitivo que se extiende por ambas partes, o un patrón más corto que comienza en el medio de la lista. Deberías buscar de forma recursiva patrones en todas las posibles sub-listas.
- Concatenar elementos y buscar coincidencias también puede perder algunos patrones. Por ejemplo, en la lista [a;b;a;b;c], tu algoritmo encontraría [a;b], pero la secuencia repetida más larga es realmente [a;b;a;b].
- Tu algoritmo también puede tener algunos pasos redundantes. Por ejemplo, una vez que encuentras un patrón coincidente, no necesitas seguir buscando concatenaciones más pequeñas de los mismos elementos.
Un enfoque más robusto sería iterar sobre la lista y mantener un seguimiento del patrón más largo encontrado hasta ahora. Puedes hacer esto manteniendo una ventana deslizante de los últimos n elementos y verificando si esa ventana coincide con alguna ventana anterior en la lista. Aquí hay algún código de muestra:
```
let rec find_longest_pattern list =
  match list with
  | [] -> []
  | x :: xs ->
    let rec check_window n window rest longest =
      match rest with
      | [] -> longest
      | y :: ys ->
        let next_window = if n >= List.length window then window else List.tl window in
        let new_window = List.append next_window [y] in
        let pattern_length = n + 1 in
        let matching_patterns = List.filter (fun wnd -> wnd = new_window) (List.tl (List.tl (List.rev_list list))) in
        match matching_patterns with
        | [] -> check_window pattern_length new_window ys longest
        | _ -> check_window pattern_length new_window ys new_window
    in
    let longest_pattern = List.fold_left (fun acc x -> if List.length x > List.length acc then x else acc) [] in
    check_window 0 [x] xs longest_pattern
```
Esta función toma una lista como entrada y devuelve el patrón repetido más largo encontrado. La función check_window verifica de forma recursiva cada ventana de tamaño n en la lista, deslizando la ventana un elemento hacia la derecha y comparándola con todas las ventanas anteriores. Si se encuentra una coincidencia, la función actualiza el patrón más largo encontrado hasta ese momento. Una vez que ha verificado todas las posibles ventanas, devuelve el patrón más largo.

La función find_longest_pattern usa fold_left para aplicar check_window a cada elemento de la lista y devuelve el patrón más largo encontrado. Ten en cuenta que este algoritmo solo considera patrones no superpuestos, por lo que devolvería [i;i] para la lista [i;i;i;i], en lugar de [i;i;i] (lo que puede o no ser deseado).

Este es solo uno de los posibles algoritmos para encontrar el patrón repetido más largo en una lista, y puede haber otros enfoques que sean más eficientes o precisos.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Encontrar la secuencia repetida más larga en una lista.

Answer

davy.ai