0votos

Contar los Palíndromos en Haskell

por josejuan hace 3 años

El problema es fácil si no se exige O(n) (ej. parece razonable que O(n^2) es fácil). Sin embargo, supuesto que podemos obtener los radios de los palíndromos en O(n) (problema que para mí *no* es fácil), entonces, se hace trivial obtener con coste lineal el desafío propuesto.

Calcular la cantidad de palíndromos existentes en una secuencia de elementos. Por ejemplo, si lo usamos con la secuencia de caracteres "sugus", los palíndromos serían: "s", "u", "g", "u", "s", "ugu", "sugus". El resultado es 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
-- Supuesto que tenemos una función `longestPalindromesFromList` que nos da 
-- los radios de los palíndromos existentes en O(n), calcular el número total de 
-- palíndromos se hace trivial, pues basta tener en cuenta que para cada palíndromo 
-- de radio `r`, es palíndromo para el mismo centro el de radio `r-1`. 
 
contar xs = length xs + (sum . map count . longestPalindromesFromList) xs 
            where count n | odd n     = (n - 1) `div` 2 
                          | otherwise =    n    `div` 2 
 
 
 
 
 
 
 
 
-- Una implementación O(n) para obtener los radios podría ser 
 
-- http://johanjeuring.blogspot.com.es/2007/08/finding-palindromes.html 
 
module Palindromes (longestPalindromesFromList) where 
 
import Data.Array 
 
longestPalindromesQ ::  Eq a => Array Int a -> [Int] 
longestPalindromesQ a  = let (afirst,alast)  = bounds a 
                             positions       = [0 .. 2*(alast-afirst+1)] 
                         in  map (lengthPalindromeAround a) positions 
 
lengthPalindromeAround  ::  Eq a => Array Int a -> Int -> Int 
lengthPalindromeAround a position 
  | even position = extendPalindromeAround (afirst+pos-1) (afirst+pos) 
  | odd  position = extendPalindromeAround (afirst+pos-1) (afirst+pos+1) 
  where  pos             =  div position 2 
         (afirst,alast)  =  bounds a 
         extendPalindromeAround start end  =  if start < 0 || end > alast-afirst || a!start /= a!end 
                                                then end-start-1 
                                                else extendPalindromeAround (start-1)  (end+1) 
 
longestPalindromes ::  Eq a => Array Int a -> [Int] 
longestPalindromes a = let (afirst,alast) = bounds a 
                       in  extendTail a afirst 0 [] 
 
extendTail a n ctail cs 
  | n > alast              = finalcs ctail cs (ctail:cs) 
  | n-ctail == afirst      = extendcs a n (ctail:cs) cs ctail 
  | a!n == a!(n-ctail-1)   = extendTail a (n+1) (ctail+2) cs 
  | otherwise              = extendcs a n (ctail:cs) cs ctail 
  where (afirst,alast) = bounds a 
 
extendcs a n cs tcs cD 
  | cD == 0           = extendTail a (n+1) 1 cs 
  | cD-1 == head tcs  = extendTail a n (head tcs) cs 
  | otherwise         = extendcs a n (min (head tcs) (cD-1):cs) (tail tcs) (cD-1) 
 
finalcs 0 tcs cs = cs 
finalcs n tcs cs = finalcs (n-1) (tail tcs) (min (head tcs) n:cs) 
 
longestPalindromesFromList :: Eq a => [a] -> [Int] 
longestPalindromesFromList xs = longestPalindromes $ array (0, length xs - 1) $ zip [0..] xs 
2 comentarios
0votos

Escrito por Fernando Pelliccioni hace 3 años

Excelente!

Supuse que la mayoría lo iba a hacer en O(n^3), que seria la version Facil.
Pero esperaba que alguien se esmere, aunque sea investigando y llegado a versiones O(n^2) que puede llegar a ser catalogada como Normal, o a la versión O(n) que es más Difícil.
Por eso lo catalogue como Normal.

La explicación del blog de Johan Jeuring es excelente.
Yo creo dedicándole el tiempo suficiente para analizarlo, uno puede llegar al mismo algoritmo...

Creo que el trabajo de Johan esta basado en...
Manacher, Glenn (1975), "A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string", Journal of the ACM 22 (3): 346–351, doi:10.1145/321892.321896.

¿Haz hecho alguna modificación al algoritmo de Johan?

Si te interesa podrias adaptarlo para Palindromic-DNA (http://en.wikipedia.org/wiki/Palindromic_sequence)
Para que puedas medir su eficiencia, aquí tienes la secuencia del Cromosoma 18 (que me proporcionó Johan), tiene una longitud aproximada de 80 millones de caracteres.

http://hgdownload.cse.ucsc.edu/goldenPath/hg19/chromosomes/chr18.fa.gz

Saludos,
Fernando.
0votos

Escrito por josejuan hace 3 años

"Yo creo dedicándole el tiempo suficiente para analizarlo, uno puede llegar al mismo algoritmo..."

Siempre intento solucionar los problemas partiendo de mi conocimiento actual, madurar el problema y, si no doy con la solución, indagar sobre aspectos que creo pueda estar relacionados (ej. combinatoria, probabilidad, ...), si tampoco, analizo problemas similares, intentando de nuevo resolverlo por mis propios medios; el ciclo se repite en base al tiempo que puedo dedicar; llegado el caso, busco las mejores soluciones e intento entenderlas.

Me temo que la idea feliz asociada a la dependencia entre sufijos y centros próximos es bastante retorcida y tengo serias dudas de que me hubiera surgido en un tiempo razonable.

No, no creo que yo lo hubiera resuelto en O(n).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.