Mayores elementos de una matriz
Enunciado
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
-- Las matrices se pueden representar mediante listas de listas. Por -- ejemplo, la matriz -- |3 2 5| -- |4 9 7| -- se puede representar por [[3,2,5],[4,9,7]]. -- -- Definir la función -- mayores :: Ord a => Int -> [[a]] -> [(a,Int)] -- tal que (mayores n xss) es la lista de los n mayores elementos de la -- matriz xss junto con sus correspondientes número de fila. Por -- ejemplo, -- ghci> mayores 4 [[4,26,9],[2,37,53],[41,1,8]] -- [(53,2),(41,3),(37,2),(26,1)] -- -- Comprobar con QuickCheck que todos los elementos de (mayores n xss) -- son mayores o iguales que los restantes elementos de xss. -- -- Nota: Se pueden usar las funciones sort y (\\) de la librería -- Data.List. |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
import Data.List (sort, (\\)) import Test.QuickCheck -- 1ª solución (con auxiliares) -- ============================ mayores1 :: Ord a => Int -> [[a]] -> [(a,Int)] mayores1 n xss = take n (reverse (sort (enumeracion xss))) -- (enumeracion xss) es la lista de los elementos de xs junto con el -- número de su fila. Por ejemplo, -- ghci> enumeracion [[4,26,9],[2,37,53],[41,1,8]] -- [(4,1),(26,1),(9,1),(2,2),(37,2),(53,2),(41,3),(1,3),(8,3)] enumeracion :: [[a]] -> [(a,Int)] enumeracion xss = [(x,i) | (xs,i) <- enumeracionFilas xss, x <- xs] -- (enumeracionFilas xss) es la lista de las filas de xs junto con su -- número. Por ejemplo, -- ghci> enumeracionFilas [[4,26,9],[2,37,53],[41,1,8]] -- [([4,26,9],1),([2,37,53],2),([41,1,8],3)] enumeracionFilas :: [[a]] -> [([a],Int)] enumeracionFilas xss = zip xss [1..] -- 2ª solución (sin auxiliares) -- ============================ mayores2 :: Ord a => Int -> [[a]] -> [(a,Int)] mayores2 n xss = take n (reverse (sort [(x,i) | (xs,i) <- zip xss [1..], x <- xs])) -- Comprobaciones -- ============== -- Las dos definiciones son equivalentes prop_equivalencia :: Int -> [[Int]] -> Bool prop_equivalencia n xss = mayores1 n xss == mayores2 n xss -- La comprobación es -- ghci> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- La propiedad de mayores es prop_mayores :: Int -> [[Int]] -> Bool prop_mayores n xss = and [x <= y | x <- elementos \\ elementosMayores, y <- elementosMayores] where elementos = concat xss elementosMayores = [x | (x,_) <- mayores1 n xss] -- La comprobación es -- ghci> quickCheck prop_mayores -- +++ OK, passed 100 tests. -- Otra forma de expresa la propiedad es prop_mayores2 :: Int -> [[Int]] -> Bool prop_mayores2 n xss = all (\x -> all (<=x) elementosRestantes) elementosMayores where elementosMayores = map fst (mayores1 n xss) elementosRestantes = concat xss \\ elementosMayores -- La comprobación es -- ghci> quickCheck prop_mayores2 -- +++ OK, passed 100 tests. |