Menu Close

Distancia de Hamming

José A. Alonso,

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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.