Mayores elementos de una matriz

José A. Alonso

17-11-2014

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 matriz xss junto con sus correspondientes número de fila. Por ejemplo,

λ> 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

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,
--    λ> 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,
--    λ> 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
--    λ> 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
--    λ> 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
--    λ> quickCheck prop_mayores2
--    +++ OK, passed 100 tests.