Menu Close

Número de parejas

José A. Alonso,

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