Menu Close

Distancia de Hamming

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre “roma” y “loba” es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

   distancia :: Eq a => [a] -> [a] -> Int

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

   distancia "romano" "comino"  ==  2
   distancia "romano" "camino"  ==  3
   distancia "roma"   "comino"  ==  2
   distancia "roma"   "camino"  ==  3
   distancia "romano" "ron"     ==  1
   distancia "romano" "cama"    ==  2
   distancia "romano" "rama"    ==  1

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

   distancia(xs,ys) = 0 si, y sólo si, xs = ys

y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

Soluciones

import Test.QuickCheck
 
-- 1ª definición:
distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y] 
 
-- 2ª definición:
distancia2 :: Eq a => [a] -> [a] -> Int
distancia2 [] ys = 0
distancia2 xs [] = 0
distancia2 (x:xs) (y:ys) | x /= y    = 1 + distancia2 xs ys
                         | otherwise = distancia2 xs ys
 
-- La propiedad es
prop_distancia1 :: [Int] -> [Int] -> Bool
prop_distancia1 xs ys =
    (distancia xs ys == 0) == (xs == ys)
 
-- La comprobación es
--    ghci> quickCheck prop_distancia1
--    *** Failed! Falsifiable (after 2 tests and 1 shrink): 
--    []
--    [1]
-- 
-- En efecto,
--    ghci> distancia [] [1] == 0
--    True
--    ghci> [] == [1]
--    False
-- 
-- La primera modificación es restringir la propiedad a lista de igual
-- longitud: 
prop_distancia2 :: [Int] -> [Int] -> Property
prop_distancia2 xs ys =
    length xs == length ys ==> 
    (distancia xs ys == 0) == (xs == ys)
 
-- La comprobación es
--    ghci> quickCheck prop_distancia2
--    *** Gave up! Passed only 33 tests.
 
-- Nota. La propiedad se verifica, pero al ser la condición demasiado
-- restringida sólo 33 de los casos la cumple.
 
-- La segunda restricción es limitar las listas a la longitud de la más
-- corta: 
prop_distancia3 :: [Int] -> [Int] -> Bool
prop_distancia3 xs ys =
    (distancia xs ys == 0) == (take n xs == take n ys)
    where n = min (length xs) (length ys)
 
-- La comprobación es
--    ghci> quickCheck prop_distancia3
--    +++ OK, passed 100 tests.

Pensamiento

En mi soledad/
he visto cosas muy claras,
que no son verdad.

Antonio Machado

Inicial

7 soluciones de “Distancia de Hamming

  1. frahidzam
    distancia :: Eq a => [a] -> [a] -> Int
    distancia xs ys = sum [1 | (a,b) <- zip xs ys , a /= b]
     
    prop_distancia :: Eq a => [a] -> [a] -> Property
    prop_distancia xs ys = distancia xs ys == 0  ==> xs == ys 
     
    -- Da errores con listas del tipo [] y [()] 
     
    -- La implicación en el otro sentido siempre se cumple
    prop_distancia' :: Eq a => [a] -> [a] -> Property
    prop_distancia' xs ys = xs == ys ==> distancia xs ys == 0
     
    -- La condición necesaria y suficiente para que se cumpla que la
    -- (distancia xs ys == 0) es que las posiciones que se comparan en
    -- los dos tienen que ser iguales. Además, tienen que ser del mismo tipo.
  2. Luis Proenza Morgado
    distancia :: Eq a => [a] -> [a] -> Int
    distancia xs ys
      | length xs < length ys =
        sum [1 | n <- [0..length xs - 1], xs !! n /= ys !! n]
      | otherwise =
        sum [1 | n <- [0..length ys - 1], xs !! n /= ys !! n]
     
    prop_distancia :: Eq a => [a] -> [a] -> Property
    prop_distancia xs ys =
      xs == ys ==> distancia xs ys==0 && distancia xs ys==0 ==> xs==ys
     
    -- El caso [] , [()] no es válido
     
    -- quickCheckWith (stdArgs {maxSize=19}) prop_distancia, el tamaño
    -- máximo debe ser 19, sino da el siguiente error
    -- "*** Gave ----up! Passed only 79 tests."
  3. sermurgar
    distancia :: Eq a => [a] -> [a] -> Int
    distancia [] ys = 0
    distancia xs [] = 0
    distancia (x:xs) (y:ys)
      | x == y    = 0 + distancia xs ys 
      | otherwise = 1 + distancia xs ys
     
    prop_distancia xs ys =
         xs == ys ==> distancia xs ys == 0
      && distancia xs ys == 0 ==> xs == ys
     
    -- λ> quickCheck prop_distancia
    -- *** Gave up! Passed only 45 tests.
     
    -- Errores en [] y [()]
  4. ireprirod
    import Test.QuickCheck
     
    distancia :: Eq a => [a] -> [a] -> Int
    distancia xs ys = sum [1 | (a,b) <- zip xs ys, a /= b]
     
    prop_distancia :: Eq a => [a] -> [a] -> Bool
    prop_distancia xs ys
      | xs == ys  = distancia xs ys == 0
      | otherwise = not (distancia xs ys == 0)
     
    -- Da errores con listas del tipo [] y [()].
     
    -- Modificando ligeramente la propiedad anterior obtenemos:
    -- distancia (xs,ys) = 0 y length(xs) = lenght(ys) si, y sólo si, xs = ys
     
    prop_distancia' :: Eq a => [a] -> [a] -> Bool
    prop_distancia' xs ys
      | length xs == length ys && distancia xs ys == 0 = xs == ys
      | otherwise                                      = xs /= ys
     
    -- Esta propiedad sí es cierta: OK, passed 100 tests.
  5. berarcmat
    distancia :: Eq a => [a] -> [a] -> Int
    distancia (x:xs) (y:ys) | x /= y     = 1 + distancia xs ys
                            | otherwise  = distancia xs ys
    distancia  _  _                      = 0
     
    prop_distancia :: Eq a => [a] -> [a] -> Property
    prop_distancia xs ys = distancia xs ys == 0  ==> xs == ys 
     
    --    λ> quickCheck prop_distancia
    --    *** Failed! Falsifiable (after 2 tests): 
    --    [()]
    --    []
     
    -- Condición necesaria y suficiente
    prop_distancia' :: Eq a => [a] -> [a] -> Property
    prop_distancia' xs ys =
      distancia xs ys == 0  && length xs == length ys
      ==> xs == ys 
     
    --    λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'
    --    +++ OK, passed 100 tests.
  6. angruicam1

    Una primera definición empleando librerías auxiliares, y una segunda sin ella

     
    import Test.QuickCheck
    import Data.List.Utils (countElem)
     
    distancia :: Eq a => [a] -> [a] -> Int
    distancia = (countElem True .) . zipWith (/=)
     
    distancia' :: Eq a => [a] -> [a] -> Int
    distancia' (x:xs) (y:ys) | x == y    = distancia' xs ys
                             | otherwise = 1 + distancia' xs ys
    distancia' _      _      = 0
     
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_distancia1 :: [Int] -> [Int] -> Bool
    prop_distancia1 xs ys =
        (distancia xs ys == 0) == (xs == ys)
     
    -- La comprobación es
    --    λ> quickCheck prop_distancia1
    --    *** Failed! Falsifiable (after 4 tests and 2 shrinks): 
    --    [0]
    --    []
    -- Efectivamente,
    --    λ> distancia [0] [] == 0
    --    True
    --    λ> [0] == []
    --    False
     
    -- Por tanto, restringimos la propiedad a listas de igual longitud: 
    prop_distancia2 :: [Int] -> [Int] -> Property
    prop_distancia2 xs ys =
        length xs == length ys ==> 
        (distancia xs ys == 0) == (xs == ys)
     
    -- La comprobación es
    --    λ> quickCheck prop_distancia2
    --    *** Gave up! Passed only 36 tests.
     
    -- La propiedad es correcta, pero la condición es demasiado
    -- restringida y sólo puede pasar 36 de los casos.
     
    -- Limitamos, por tanto, las listas a la longitud de la más corta: 
    prop_distancia3 :: [Int] -> [Int] -> Bool
    prop_distancia3 xs ys =
        (distancia xs ys == 0) == (take n xs == take n ys)
        where n = min (length xs) (length ys)
     
    -- La comprobación es
    --    λ> quickCheck prop_distancia3
    --    +++ OK, passed 100 tests.
  7. javmarcha1
    distancia :: Eq a => [a] -> [a] -> Int
    distancia xs ys = length [(a,b) | (a,b) <- zip xs ys , a /= b] 
     
    prop_distancia :: Eq a => [a] -> [a] -> Property
    prop_distancia xs ys = distancia xs ys == 0 ==> xs == ys
     
    -- λ> quickCheck prop_distancia2
    -- *** Failed! Falsifiable (after 2 tests): 
    -- [()]
    -- []
     
    -- Condición necesaria y suficiente
     
    prop_distancia' :: Eq a => [a] -> [a] -> Property
    prop_distancia' xs ys =
      distancia xs ys == 0  && length xs == length ys ==> xs == ys 
     
    -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_distancia'
    -- +++ OK, passed 100 tests.

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.