Menu Close

Número de parejas

Definir la función

   nParejas :: Ord a => [a] -> Int

tal que (nParejas xs) es el número de parejas de elementos iguales en xs. Por ejemplo,

   nParejas [1,2,2,1,1,3,5,1,2]        ==  3
   nParejas [1,2,1,2,1,3,2]            ==  2
   nParejas [1..2*10^6]                ==  0
   nParejas2 ([1..10^6] ++ [1..10^6])  ==  1000000

En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el segundo ejemplo, las parejas son (1,1) y (2,2).

Comprobar con QuickCheck que para toda lista de enteros xs, el número de parejas de xs es igual que el número de parejas de la inversa de xs.

Soluciones

import Test.QuickCheck
import Data.List ((\\), group, sort)
 
-- 1ª solución
nParejas :: Ord a => [a] -> Int
nParejas []     = 0
nParejas (x:xs) | x `elem` xs = 1 + nParejas (xs \\ [x])
                | otherwise   = nParejas xs
 
-- 2ª solución
nParejas2 :: Ord a => [a] -> Int
nParejas2 xs =
  sum [length ys `div` 2 | ys <- group (sort xs)]
 
-- 3ª solución
nParejas3 :: Ord a => [a] -> Int
nParejas3 = sum . map (`div` 2). map length . group . sort
 
-- 4ª solución
nParejas4 :: Ord a => [a] -> Int
nParejas4 = sum . map ((`div` 2) . length) . group . sort
 
-- Equivalencia
prop_equiv :: [Int] -> Bool
prop_equiv xs =
  nParejas xs == nParejas2 xs &&
  nParejas xs == nParejas3 xs &&
  nParejas xs == nParejas4 xs 
 
-- Comprobación:
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
--    λ> nParejas [1..20000]
--    0
--    (2.54 secs, 4,442,808 bytes)
--    λ> nParejas2 [1..20000]
--    0
--    (0.03 secs, 12,942,232 bytes)
--    λ> nParejas3 [1..20000]
--    0
--    (0.02 secs, 13,099,904 bytes)
--    λ> nParejas4 [1..20000]
--    0
--    (0.01 secs, 11,951,992 bytes)
 
-- Propiedad:
prop_nParejas :: [Int] -> Bool
prop_nParejas xs =
  nParejas xs == nParejas (reverse xs)
 
-- Comprobación:
--    λ> quickCheck prop_nParejas
--    +++ OK, passed 100 tests.

Pensamiento

Toda la imaginería
que no ha brotado del río,
barata bisutería.

Antonio Machado

Inicial

7 soluciones de “Número de parejas

  1. lucsanand
    nParejas :: Ord a => [a] -> Int
    nParejas [] = 0
    nParejas (x:xs)
      | even (frecuencia (x:xs) x) = 1 + nParejas xs
      | otherwise                  = nParejas xs
     
    frecuencia :: Eq a => [a] -> a -> Int
    frecuencia xs n = sum [1 | a <- xs, a == n]
  2. luipromor
    import Data.List (nub)
    import Test.QuickCheck
     
    nParejas :: Ord a => [a] -> Int
    nParejas xs = sum [f (filter (n==) xs) | n <- nub xs]
      where f ys | even  (length ys) = div (length ys) 2
                 | otherwise         = div (length ys) 2
     
    prop_nParejas :: [Int] -> Bool  
    prop_nParejas xs =
      nParejas xs == (nParejas . reverse) xs
    • luipromor
      import Data.List (nub)
      import Test.QuickCheck
       
      nParejas :: Ord a => [a] -> Int
      nParejas xs = sum [f (filter (n==) xs) | n <- nub xs]
        where f ys = div (length ys) 2
       
      prop_nParejas :: [Int] -> Bool  
      prop_nParejas xs = nParejas xs == (nParejas . reverse) xs
  3. ireprirod
    import Data.List (nub)
     
    nParejas :: Eq a => [a] -> Int
    nParejas = cuenta . parejas
     
    parejas :: Eq a => [a] -> [[a]]
    parejas xs = [filter (y==) xs |  y <- nub xs]
     
    cuenta :: [[a]] -> Int
    cuenta = cuentaAux 0
      where cuentaAux v []       = v
            cuentaAux v (xs:xss) = cuentaAux (v + (l xs)) xss
     
    l :: [a] -> Int
    l xs = div (length xs) 2
  4. frahidzam
    import Data.List (group, sort, nub)
    import Test.QuickCheck
     
    nParejas :: Ord a => [a] -> Int
    nParejas xs = sum [b | (c,b) <- aux xs]
     
    aux :: Ord a => [a] -> [(a,Int)]
    aux xs = zip (sort (nub xs)) (ocur2 xs)
     
    ocur2 :: Ord a => [a] ->[Int]
    ocur2 xs = [div x 2 | x <- ocur xs]
     
    ocur :: Ord a => [a] ->[Int]
    ocur xs = map length (group (sort xs))
     
    prop_nParejas :: [Int] -> Bool  
    prop_nParejas xs =
      nParejas xs == (nParejas . reverse) xs
  5. berarcmat
    import Data.List (group, sort)
    import Test.QuickCheck
     
    nParejas :: Ord a => [a] -> Int
    nParejas = sum. map (`div` 2). map (length) . group. concat. sort. group
     
    prop_nParejas :: [Int] -> Bool  
    prop_nParejas xs =
      nParejas xs == (nParejas . reverse) xs
  6. javmarcha1
    import Test.QuickCheck
    import Data.List (nub)
     
    nParejas :: Ord a => [a] -> Int
    nParejas xs | xs == nub xs = 0
                | otherwise    = sum [div x 2 | x <- listaaparece xs]
     
    listaaparece :: Eq a => [a] -> [Int] 
    listaaparece xs = [aparece x xs | x <- nub xs]
     
    aparece :: Eq a => a -> [a] -> Int
    aparece _ [] = 0
    aparece x (y:ys) | x == y    = 1 + aparece x ys
                     | otherwise = aparece x ys
     
    prop_nParejas :: [Int] -> Bool  
    prop_nParejas xs =
      nParejas xs == (nParejas . reverse) xs

Escribe tu solución

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