Ir al contenido principal

Anagramas


Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, "mora" y "roma" son anagramas de "amor".

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.


1. Soluciones en Haskell

module Anagramas where

import Data.List (delete, sort, permutations)
import Data.Char (toLower)
import Data.Function (on)
import Data.Map (Map, fromListWith)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución
-- ===========

anagramas :: String -> [String] -> [String]
anagramas _ [] = []
anagramas x (y:ys)
  | sonAnagramas x y = y : anagramas x ys
  | otherwise        = anagramas x ys

-- (sonAnagramas xs ys) se verifica si xs e ys son anagramas. Por
-- ejemplo,
--    sonAnagramas "amor" "Roma"  ==  True
--    sonAnagramas "amor" "mola"  ==  False
sonAnagramas :: String -> String -> Bool
sonAnagramas xs ys =
  sort (map toLower xs) == sort (map toLower ys)

-- 2ª solución
-- =============

anagramas2 :: String -> [String] -> [String]
anagramas2 _ [] = []
anagramas2 x (y:ys)
  | sonAnagramas2 x y = y : anagramas2 x ys
  | otherwise         = anagramas2 x ys

sonAnagramas2 :: String -> String -> Bool
sonAnagramas2 xs ys =
  (sort . map toLower) xs == (sort . map toLower) ys

-- 3ª solución
-- ===========

anagramas3 :: String -> [String] -> [String]
anagramas3 _ [] = []
anagramas3 x (y:ys)
  | sonAnagramas3 x y = y : anagramas3 x ys
  | otherwise         = anagramas3 x ys

sonAnagramas3 :: String -> String -> Bool
sonAnagramas3 = (==) `on` (sort . map toLower)

-- Nota. En la solución anterior se usa la función on ya que
--    (f `on` g) x y
-- es equivalente a
--    f (g x) (g y)
-- Por ejemplo,
--    λ> ((*) `on` (+2)) 3 4
--    30

-- 4ª solución
-- ===========

anagramas4 :: String -> [String] -> [String]
anagramas4 x ys = [y | y <- ys, sonAnagramas x y]

-- 5ª solución
-- ===========

anagramas5 :: String -> [String] -> [String]
anagramas5 x = filter (`sonAnagramas` x)

-- 6ª solución
-- ===========

anagramas6 :: String -> [String] -> [String]
anagramas6 x = filter (((==) `on` (sort . map toLower)) x)

-- 7ª solución
-- ===========

anagramas7 :: String -> [String] -> [String]
anagramas7 _ [] = []
anagramas7 x (y:ys)
  | sonAnagramas7 x y = y : anagramas7 x ys
  | otherwise         = anagramas7 x ys

sonAnagramas7 :: String -> String -> Bool
sonAnagramas7 xs ys = aux (map toLower xs) (map toLower ys)
  where
    aux [] [] = True
    aux [] _  = False
    aux (u:us) vs | u `notElem` vs = False
                  | otherwise      = aux us (delete u vs)

-- 8ª solución
-- ===========

anagramas8 :: String -> [String] -> [String]
anagramas8 x = filter (`sonAnagramas8` x)

sonAnagramas8 :: String -> String -> Bool
sonAnagramas8 xs ys =
  frecuencias (map toLower xs) == frecuencias (map toLower ys)

frecuencias :: String -> Map Char Int
frecuencias xs = fromListWith (+) (zip xs (repeat 1))

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (String -> [String] -> [String]) -> Spec
specG anagramas' = do
  it "e1" $
    anagramas' "amor" ["Roma","mola","loma","moRa", "rama"] `shouldBe`
    ["Roma","moRa"]
  it "e2" $
    anagramas' "rama" ["aMar","amaRa","roMa","marr","aRma"] `shouldBe`
    ["aMar","aRma"]

spec :: Spec
spec = do
  describe "def. 1" $ specG anagramas
  describe "def. 2" $ specG anagramas2
  describe "def. 3" $ specG anagramas3
  describe "def. 4" $ specG anagramas4
  describe "def. 5" $ specG anagramas5
  describe "def. 6" $ specG anagramas6
  describe "def. 7" $ specG anagramas7
  describe "def. 8" $ specG anagramas8

-- La verificación es
--    λ> verifica
--    16 examples, 0 failures

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> ej = take (10^6) (permutations "1234567890")
--    λ> length (anagramas "1234567890" ej)
--    1000000
--    (2.27 secs, 5,627,236,104 bytes)
--    λ> length (anagramas2 "1234567890" ej)
--    1000000
--    (2.80 secs, 5,513,260,584 bytes)
--    λ> length (anagramas3 "1234567890" ej)
--    1000000
--    (1.86 secs, 5,097,260,856 bytes)
--    λ> length (anagramas4 "1234567890" ej)
--    1000000
--    (2.25 secs, 5,073,260,632 bytes)
--    λ> length (anagramas5 "1234567890" ej)
--    1000000
--    (2.14 secs, 5,009,260,616 bytes)
--    λ> length (anagramas6 "1234567890" ej)
--    1000000
--    (1.58 secs, 4,977,260,976 bytes)
--    λ> length (anagramas7 "1234567890" ej)
--    1000000
--    (6.63 secs, 6,904,821,648 bytes)
--    λ> length (anagramas8 "1234567890" ej)
--    1000000
--    (3.90 secs, 9,679,323,632 bytes)

-- (cadena n) es la cadena de los 10 primeros caracteres de la cadena
-- infinita abcabcabc... Por ejemplo,
--    cadena 10  ==  "abcabcabca"
cadena :: Int -> String
cadena n = take n (cycle "abc")

-- (cadenas m n) es la lista otenida repitiendo m veces (adena n). Por
-- ejemplo,
--    cadenas 3 10 == ["abcabcabca","abcabcabca","abcabcabca"]
cadenas :: Int -> Int -> [String]
cadenas m n = replicate m (cadena n)

--    λ> length (anagramas6 (cadena (10^5)) (cadenas 100 (10^5)))
--    100
--    (8.42 secs, 23,126,067,704 bytes)
--    λ> length (anagramas8 (cadena (10^5)) (cadenas 100 (10^5)))
--    100
--    (4.06 secs, 7,220,705,856 bytes)