# Determinación de los elementos minimales

Definir la función

` minimales :: Ord a => [[a]] -> [[a]]`

tal que (minimales xss) es la lista de los elementos de xss que no están contenidos en otros elementos de xss. Por ejemplo,

``` minimales [[1,3],[2,3,1],[3,2,5]] == [[2,3,1],[3,2,5]] minimales [[1,3],[2,3,1],[3,2,5],[3,1]] == [[2,3,1],[3,2,5]] map sum (minimales [[1..n] | n <- [1..300]]) == [45150]```

#### Soluciones

```import Data.List (delete, nub) import Test.QuickCheck (quickCheck)   -- 1ª solución -- ===========   minimales :: Ord a => [[a]] -> [[a]] minimales xss = [xs | xs <- xss, null [ys | ys <- xss, subconjuntoPropio xs ys]]   -- (subconjuntoPropio xs ys) se verifica si xs es un subconjunto propio -- de ys. Por ejemplo, -- subconjuntoPropio [1,3] [3,1,3] == False -- subconjuntoPropio [1,3,1] [3,1,2] == True subconjuntoPropio :: Ord a => [a] -> [a] -> Bool subconjuntoPropio xs ys = aux (nub xs) (nub ys) where aux _ [] = False aux [] _ = True aux (u:us) vs = u `elem` vs && aux us (delete u vs)   -- 2ª solución -- ===========   minimales2 :: Ord a => [[a]] -> [[a]] minimales2 xss = [xs | xs <- xss, null [ys | ys <- xss, subconjuntoPropio2 xs ys]]   subconjuntoPropio2 :: Ord a => [a] -> [a] -> Bool subconjuntoPropio2 xs ys = subconjunto xs ys && not (subconjunto ys xs)   -- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por -- ejemplo, -- subconjunto [1,3] [3,1,3] == True -- subconjunto [1,3,1,3] [3,1,3] == True -- subconjunto [1,3,2,3] [3,1,3] == False -- subconjunto [1,3,1,3] [3,1,3,2] == True subconjunto :: Ord a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs   -- Equivalencia de las definiciones -- ================================   -- La propiedad es prop_minimales :: [[Int]] -> Bool prop_minimales xss = minimales xss == minimales2 xss   verifica_minimales :: IO () verifica_minimales = quickCheck prop_minimales   -- La comprobación es -- λ> verifica_minimales -- +++ OK, passed 100 tests.   -- Comparación de eficiencia -- =========================   -- La comparación es -- λ> length (minimales [[1..n] | n <- [1..200]]) -- 1 -- (2.30 secs, 657,839,560 bytes) -- λ> length (minimales2 [[1..n] | n <- [1..200]]) -- 1 -- (0.84 secs, 101,962,480 bytes)```

El código se encuentra en GitHub.

## 2 soluciones de “Determinación de los elementos minimales”

1. Chema Cortes
```import Data.List (())   minimales :: Ord a => [[a]] -> [[a]] minimales [] = [] minimales (xs : xss) | any (xs ⊆) xss = minimales xss | otherwise = xs : minimales (filter (⊈ xs) xss) where xs ⊆ ys = null \$ xs ys xs ⊈ ys = not \$ xs ⊆ ys```
2. David Escalona
```import Data.List (delete, nub)   minimales :: Ord a => [[a]] -> [[a]] minimales xss = [xs | xs <- xss, null [ys | ys <- xss, subconjuntoPropio xs ys]]   subconjuntoPropio :: Ord a => [a] -> [a] -> Bool subconjuntoPropio xs ys = aux (nub xs) (nub ys) where aux _ [] = False aux [] _ = True aux (u:us) vs = u `elem` vs && aux us (delete u vs)```

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