1votos

Pangram & Isogram en Haskell

por josejuan hace 2 meses

Tres implementaciones diferentes con costes O(n log n), O(n log K) y O(n).

Implementar la función isPangram y isIsogram.

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
import qualified Data.Set as Set 
import Data.List 
import Data.Char 
import Data.Bits 
 
abc = ['a'..'z'] 
 
prepare = filter (`elem` abc) . map toLower 
 
-- O(n log n) 
isPangram1 = (abc ==) . uniq . sort . prepare 
 
-- O(n log min{n, |S|}) 
isPangram2 = (abc ==) . Set.elems . Set.fromList . prepare 
 
-- O(n) 
isPangram3 = ((2^(length abc) - 1) ==) . foldl' (\m x -> m .|. (1 `shiftL` (ord x - 97))) (0 :: Int) . prepare 
 
-- O(n log n) 
isIsogram1 = all ((1 ==) . length) . group . sort . prepare 
 
-- O(n log min{n, |S|}) 
isIsogram2 = check Set.empty . prepare 
  where check s (x:xs) | x `Set.member` s = False 
                       | otherwise        = check (Set.insert x s) xs 
        check _     _                     = True 
 
-- O(n) 
isIsogram3 = check (0 :: Int) . prepare 
  where check s (x:xs) | s .&. m /= 0 = False 
                       | otherwise    = check (s .|. m) xs 
                         where m = 1 `shiftL` (ord x - 97) 
        check _     _                 = True 
 
 
uniq :: Eq a => [a] -> [a] 
uniq (x:y:zs) | x == y    =    uniq (y:zs) 
              | otherwise = x: uniq (y:zs) 
uniq      zs              =            zs 
8 comentarios
0votos

Escrito por AverageUser hace 2 meses

Mhh, que eficiencia crees que tendría esta?:
isIsogram :: String -> Bool
isIsogram = fn . map toLower
  where fn []     = True
        fn (x:xs) = if isLetter x && x `elem` xs then False else fn xs
0votos

Escrito por AverageUser hace 2 meses

podrias escribir la tuya así también:

isIsogram1 :: String -> Bool
isIsogram1 = all ((1==) . length) . group . sort . filter isLetter . map toLower
0votos

Escrito por josejuan hace 2 meses

O(n^2) porque para cada x recorre xs (en particular para n chars diferentes sean o no del alfabeto como los espacios, es T = n (n - 1) / 2).
0votos

Escrito por josejuan hace 2 meses

Y si isLetter representa el alfabeto (mis algs no lo presuponen) entonces O(n |S|), dado que elems no será nunca evaluado más del tamaño del alfabeto.
0votos

Escrito por josejuan hace 2 meses

Bueno, realmente O(n min{n, |S|}), considerando cadenas de tamaño menor que el alfabeto.
0votos

Escrito por AverageUser hace 2 meses

isLetter viene de Data.Char (no lo puse) y bueno lo que hace es medio obvio.
0votos

Escrito por josejuan hace 2 meses

El que ha fallado entonces es el "otro medio" ;):
> isLetter 'ñ'
True
>

Por eso he puesto como cota primera O(n^2), porque tu implementación no cumple el enunciado del desafío ("...sin la ñ..."). Pero vamos, no tiene ninguna importancia, se entiende perfectamente la intención y es correcta.
0votos

Escrito por AverageUser hace 2 meses

jaja, tienes razón. no se me ocurrió probar con la ñ

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.