partition – Exercitium

Separación por posición

José A. Alonso, 15-abril-2022, Ejercicio

Definir la función

   particion :: [a] -> ([a],[a])

tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,

   particion [3,5,6,2]    ==  ([3,6],[5,2])
   particion [3,5,6,2,7]  ==  ([3,6,7],[5,2])
   particion "particion"  ==  ("priin","atco")

Soluciones

module Separacion_por_posicion where
 
import Data.List (partition)
import qualified Data.Vector as V ((!), fromList, length)
import Test.QuickCheck (quickCheck)
 
-- 1ª solución
-- ===========
 
particion1 :: [a] -> ([a],[a])
particion1 xs = ([x | (n,x) <- nxs, even n],
                 [x | (n,x) <- nxs, odd n])
  where nxs = enumeracion xs
 
--(numeracion xs) es la enumeración de xs. Por ejemplo,
--    enumeracion [7,9,6,8]  ==  [(0,7),(1,9),(2,6),(3,8)]
enumeracion :: [a] -> [(Int,a)]
enumeracion = zip [0..]
 
-- 2ª solución
-- ===========
 
particion2 :: [a] -> ([a],[a])
particion2 []     = ([],[])
particion2 (x:xs) = (x:zs,ys)
  where (ys,zs) = particion2 xs
 
-- 3ª solución
-- ===========
 
particion3 :: [a] -> ([a],[a])
particion3 = foldr f ([],[])
  where f x (ys,zs) = (x:zs,ys)
 
-- 4ª solución
-- ===========
 
particion4 :: [a] -> ([a],[a])
particion4 = foldr (\x (ys,zs) -> (x:zs,ys)) ([],[])
 
-- 5ª solución
-- ===========
 
particion5 :: [a] -> ([a],[a])
particion5 xs =
  ([xs!!k | k <- [0,2..n]],
   [xs!!k | k <- [1,3..n]])
  where n = length xs - 1
 
-- 6ª solución
-- ===========
 
particion6 :: [a] -> ([a],[a])
particion6 xs = (pares xs, impares xs)
 
-- (pares xs) es la lista de los elementos de xs en posiciones
-- pares. Por ejemplo,
--    pares [3,5,6,2]  ==  [3,6]
pares :: [a] -> [a]
pares []     = []
pares (x:xs) = x : impares xs
 
-- (impares xs) es la lista de los elementos de xs en posiciones
-- impares. Por ejemplo,
--    impares [3,5,6,2]  ==  [5,2]
impares :: [a] -> [a]
impares []     = []
impares (_:xs) = pares xs
 
-- 7ª solución
-- ===========
 
particion7 :: [a] -> ([a],[a])
particion7 [] = ([],[])
particion7 xs =
  ([v V.! k | k <- [0,2..n-1]],
   [v V.! k | k <- [1,3..n-1]])
  where v = V.fromList xs
        n = V.length v
 
-- 8ª solución
-- ===========
 
particion8 :: [a] -> ([a],[a])
particion8 xs =
  (map snd ys, map snd zs)
  where (ys,zs) = partition posicionPar (zip [0..] xs)
 
posicionPar :: (Int,a) -> Bool
posicionPar = even . fst
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_particion :: [Int] -> Bool
prop_particion xs =
  all (== particion1 xs)
      [particion2 xs,
       particion3 xs,
       particion4 xs,
       particion5 xs,
       particion6 xs,
       particion7 xs,
       particion8 xs]
 
-- La comprobación es
--    λ> quickCheck prop_particion
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> last (snd (particion1 [1..6*10^6]))
--    6000000
--    (2.74 secs, 2,184,516,080 bytes)
--    λ> last (snd (particion2 [1..6*10^6]))
--    6000000
--    (2.02 secs, 1,992,515,880 bytes)
--    λ> last (snd (particion3 [1..6*10^6]))
--    6000000
--    (3.17 secs, 1,767,423,240 bytes)
--    λ> last (snd (particion4 [1..6*10^6]))
--    6000000
--    (3.23 secs, 1,767,423,240 bytes)
--    λ> last (snd (particion5 [1..6*10^6]))
--    6000000
--    (1.62 secs, 1,032,516,192 bytes)
--    λ> last (snd (particion5 [1..6*10^6]))
--    6000000
--    (1.33 secs, 1,032,516,192 bytes)
--    λ> last (snd (particion6 [1..6*10^6]))
--    6000000
--    (1.80 secs, 888,515,960 bytes)
--    λ> last (snd (particion7 [1..6*10^6]))
--    6000000
--    (1.29 secs, 1,166,865,672 bytes)
--    λ> last (snd (particion8 [1..6*10^6]))
--    6000000
--    (0.87 secs, 3,384,516,616 bytes)
--
--    λ> last (snd (particion5 [1..10^7]))
--    10000000
--    (1.94 secs, 1,720,516,872 bytes)
--    λ> last (snd (particion7 [1..10^7]))
--    10000000
--    (2.54 secs, 1,989,215,176 bytes)
--    λ> last (snd (particion8 [1..10^7]))
--    10000000
--    (1.33 secs, 5,640,516,960 bytes)

module Separacion_por_posicion where import Data.List (partition) import qualified Data.Vector as V ((!), fromList, length) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== particion1 :: [a] -> ([a],[a]) particion1 xs = ([x | (n,x) <- nxs, even n], [x | (n,x) <- nxs, odd n]) where nxs = enumeracion xs --(numeracion xs) es la enumeración de xs. Por ejemplo, -- enumeracion [7,9,6,8] == [(0,7),(1,9),(2,6),(3,8)] enumeracion :: [a] -> [(Int,a)] enumeracion = zip [0..] -- 2ª solución -- =========== particion2 :: [a] -> ([a],[a]) particion2 [] = ([],[]) particion2 (x:xs) = (x:zs,ys) where (ys,zs) = particion2 xs -- 3ª solución -- =========== particion3 :: [a] -> ([a],[a]) particion3 = foldr f ([],[]) where f x (ys,zs) = (x:zs,ys) -- 4ª solución -- =========== particion4 :: [a] -> ([a],[a]) particion4 = foldr (\x (ys,zs) -> (x:zs,ys)) ([],[]) -- 5ª solución -- =========== particion5 :: [a] -> ([a],[a]) particion5 xs = ([xs!!k | k <- [0,2..n]], [xs!!k | k <- [1,3..n]]) where n = length xs - 1 -- 6ª solución -- =========== particion6 :: [a] -> ([a],[a]) particion6 xs = (pares xs, impares xs) -- (pares xs) es la lista de los elementos de xs en posiciones -- pares. Por ejemplo, -- pares [3,5,6,2] == [3,6] pares :: [a] -> [a] pares [] = [] pares (x:xs) = x : impares xs -- (impares xs) es la lista de los elementos de xs en posiciones -- impares. Por ejemplo, -- impares [3,5,6,2] == [5,2] impares :: [a] -> [a] impares [] = [] impares (_:xs) = pares xs -- 7ª solución -- =========== particion7 :: [a] -> ([a],[a]) particion7 [] = ([],[]) particion7 xs = ([v V.! k | k <- [0,2..n-1]], [v V.! k | k <- [1,3..n-1]]) where v = V.fromList xs n = V.length v -- 8ª solución -- =========== particion8 :: [a] -> ([a],[a]) particion8 xs = (map snd ys, map snd zs) where (ys,zs) = partition posicionPar (zip [0..] xs) posicionPar :: (Int,a) -> Bool posicionPar = even . fst -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_particion :: [Int] -> Bool prop_particion xs = all (== particion1 xs) [particion2 xs, particion3 xs, particion4 xs, particion5 xs, particion6 xs, particion7 xs, particion8 xs] -- La comprobación es -- λ> quickCheck prop_particion -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (snd (particion1 [1..6*10^6])) -- 6000000 -- (2.74 secs, 2,184,516,080 bytes) -- λ> last (snd (particion2 [1..6*10^6])) -- 6000000 -- (2.02 secs, 1,992,515,880 bytes) -- λ> last (snd (particion3 [1..6*10^6])) -- 6000000 -- (3.17 secs, 1,767,423,240 bytes) -- λ> last (snd (particion4 [1..6*10^6])) -- 6000000 -- (3.23 secs, 1,767,423,240 bytes) -- λ> last (snd (particion5 [1..6*10^6])) -- 6000000 -- (1.62 secs, 1,032,516,192 bytes) -- λ> last (snd (particion5 [1..6*10^6])) -- 6000000 -- (1.33 secs, 1,032,516,192 bytes) -- λ> last (snd (particion6 [1..6*10^6])) -- 6000000 -- (1.80 secs, 888,515,960 bytes) -- λ> last (snd (particion7 [1..6*10^6])) -- 6000000 -- (1.29 secs, 1,166,865,672 bytes) -- λ> last (snd (particion8 [1..6*10^6])) -- 6000000 -- (0.87 secs, 3,384,516,616 bytes) -- -- λ> last (snd (particion5 [1..10^7])) -- 10000000 -- (1.94 secs, 1,720,516,872 bytes) -- λ> last (snd (particion7 [1..10^7])) -- 10000000 -- (2.54 secs, 1,989,215,176 bytes) -- λ> last (snd (particion8 [1..10^7])) -- 10000000 -- (1.33 secs, 5,640,516,960 bytes)

El código se encuentra en GitHub.

La elaboración de las soluciones se describe en el siguiente vídeo

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Leer más →

Clases de equivalencia

José A. Alonso, 5-abril-2018, Medio

Definir la función

   clasesEquivalencia :: Ord a => 
                         Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

   ghci> let c = fromList [-3..3]
   ghci> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
   fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
   ghci> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
   fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Soluciones

import Data.Set as S
 
clasesEquivalencia :: Ord a => 
                      Set a -> (a -> a -> Bool) -> Set (Set a)
clasesEquivalencia xs r 
    | S.null xs =  empty
    | otherwise =  us `insert` clasesEquivalencia vs r
    where (y,ys)  = deleteFindMin xs
          (us,vs) = partition (r y) xs

Leer más →

Clases de equivalencia

José A. Alonso, 13-abril-2017, Avanzado

Definir la función

   clasesEquivalencia :: Ord a => 
                         Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

   ghci> let c = fromList [-3..3]
   ghci> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
   fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
   ghci> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
   fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Soluciones

import Data.Set as S
 
clasesEquivalencia :: Ord a => 
                      Set a -> (a -> a -> Bool) -> Set (Set a)
clasesEquivalencia xs r 
    | S.null xs =  empty
    | otherwise =  us `insert` clasesEquivalencia vs r
    where (y,ys)  = deleteFindMin xs
          (us,vs) = partition (r y) xs

Leer más →

Agrupación por orden de aparición

José A. Alonso, 13-diciembre-2016, Medio

Definir la función

   agrupacion :: Eq a => [a] -> [a]

tal que (agrupacion xs) es la lista obtenida agrupando los elementos de xs según su primera aparición. Por ejemplo,

   agrupacion [3,1,5,1,7,1,5,3]  ==  [3,3,1,1,1,5,5,7]
   agrupacion "babcacb"          ==  "bbbaacc"

Soluciones

import Data.List (nub, partition)
 
-- 1ª definición
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) =
  x : filter (==x) xs ++ agrupacion (filter (/=x) xs)
 
-- 2ª definición
agrupacion2 :: Eq a => [a] -> [a]
agrupacion2 xs = concat [filter (x==) xs | x <- nub xs]
 
-- 3ª definición
agrupacion3 :: Eq a => [a] -> [a]
agrupacion3 []     = []
agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs
  where (ys,zs) = partition (==x) xs
 
-- Comparación de eficiencia
--    λ> import Data.List (cycle)
--    λ> :set +s
--    λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (24.40 secs, 3,173,123,368 bytes)
--    λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (13.71 secs, 2,333,129,416 bytes)
--    λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3])))
--    15000000
--    (22.33 secs, 5,080,127,944 bytes)

Leer más →

Clases de equivalencia

José A. Alonso, 5-abril-2016, Inicial

Definir la función

   clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]

tal que (clasesEquivalencia xs r) es la lista de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

   λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3)
   [[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]]
   λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0)
   [[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]]
   λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y)
   [[-4,4],[-3,3],[-2,2],[-1,1],[0]]

Soluciones

import Data.List (partition)
 
clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]
clasesEquivalencia [] r = []
clasesEquivalencia ys@(x:xs) r =
    us : clasesEquivalencia vs r
    where (us,vs) = partition (r x) ys

Solución en Maxima

clasesEquivalencia (xs,r) :=
  equiv_classes (setify (xs),r)$

La evaluación de los ejemplos es

(%i6) xs : makelist (k,k,1,10)$
(%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0)));
(%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}}
(%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0)));
(%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}}
(%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y))));
(%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}}

Leer más →

Etiqueta: partition

Separación por posición

Soluciones

Nuevas soluciones

Clases de equivalencia

Soluciones

Clases de equivalencia

Soluciones

Agrupación por orden de aparición

Soluciones

Clases de equivalencia

Soluciones

Solución en Maxima

Subscribe to Blog via Email

Entradas recientes

Etiquetas