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

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]

import Data.List (delete, nub)
import Data.Set (fromList, isProperSubsetOf)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

minimales1 :: Ord a => [[a]] -> [[a]]
minimales1 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

-- 3ª solución
-- ===========

minimales3 :: Ord a => [[a]] -> [[a]]
minimales3 xss =
  [xs | xs <- xss,
        null [ys | ys <- xss, subconjuntoPropio3 xs ys]]

subconjuntoPropio3 :: Ord a => [a] -> [a] -> Bool
subconjuntoPropio3 xs ys =
  isProperSubsetOf (fromList xs) (fromList ys)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([[Int]] -> [[Int]]) -> Spec
specG minimales = do
  it "e1" $
    minimales [[1,3],[2,3,1],[3,2,5]]        `shouldBe`  [[2,3,1],[3,2,5]]
  it "e2" $
    minimales [[1,3],[2,3,1],[3,2,5],[3,1]]  `shouldBe`  [[2,3,1],[3,2,5]]

spec :: Spec
spec = do
  describe "def. 1" $ specG minimales1
  describe "def. 2" $ specG minimales2
  describe "def. 3" $ specG minimales3

-- La verificación es
--    λ> verifica
--    6 examples, 0 failures

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_minimales :: [[Int]] -> Bool
prop_minimales xss =
  all (== minimales1 xss)
      [minimales2 xss,
       minimales3 xss]

-- La comprobación es
--    λ> quickCheck prop_minimales
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (minimales1 [[1..n] | n <- [1..200]])
--    1
--    (2.07 secs, 702,257,168 bytes)
--    λ> length (minimales2 [[1..n] | n <- [1..200]])
--    1
--    (0.85 secs, 138,498,288 bytes)
--    λ> length (minimales3 [[1..n] | n <- [1..200]])
--    1
--    (0.15 secs, 293,134,464 bytes)
--
--    λ> length (minimales2 [[1..n] | n <- [1..300]])
--    1
--    (3.61 secs, 442,569,888 bytes)
--    λ> length (minimales3 [[1..n] | n <- [1..300]])
--    1
--    (0.39 secs, 981,990,968 bytes)

from collections import Counter
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

# 1ª solución
# ===========

# subconjuntoPropio(xs, ys) se verifica si xs es un subconjunto propio
# de ys. Por ejemplo,
#    subconjuntoPropio1([1,3], [3,1,3])    ==  False
#    subconjuntoPropio1([1,3,1], [3,1,2])  ==  True
def subconjuntoPropio1(xs: list[A],
                       ys: list[A]) -> bool:
    def aux(ws: list[A], vs: list[A]) -> bool:
        if not vs:
            return False
        if not ws:
            return True
        u, us = ws[0], ws[1:]
        if u in vs:
            vs.remove(u)
            return aux(us, vs)
        return False
    return aux(list(Counter(xs).keys()), list(Counter(ys).keys()))

def minimales1(xss: list[list[A]]) -> list[list[A]]:
    return [xs for xs in xss
            if not any(subconjuntoPropio1(xs, ys) for ys in xss)]

# 2ª solución
# ===========

# 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
def subconjunto(xs: list[A],
                ys: list[A]) -> bool:
    return all(x in ys for x in xs)

def subconjuntoPropio2(xs: list[A],
                       ys: list[A]) -> bool:
    return subconjunto(xs, ys) and not subconjunto(ys, xs)

def minimales2(xss: list[list[A]]) -> list[list[A]]:
    return [xs for xs in xss
            if not any(subconjuntoPropio2(xs, ys) for ys in xss)]

# 3ª solución
# ===========

def subconjuntoPropio3(xs: list[A],
                       ys: list[A]) -> bool:
    return set(xs) < set(ys)

def minimales3(xss: list[list[A]]) -> list[list[A]]:
    return [xs for xs in xss
            if not any(subconjuntoPropio3(xs, ys) for ys in xss)]

# Verificación
# ============

def test_minimales() -> None:
    for minimales in [minimales1, minimales2, minimales3]:
        assert minimales([[1,3],[2,3,1],[3,2,5]]) == [[2,3,1],[3,2,5]]
        assert minimales([[1,3],[2,3,1],[3,2,5],[3,1]]) == [[2,3,1],[3,2,5]]
    print("Verificado")

# La verificación es
#    >>> test_minimales()
#    Verificado

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.lists(st.lists(st.integers()), min_size=1))
def test_minimales_equiv(xss: list[list[int]]) -> None:
    r = minimales1(xss)
    assert minimales2(xss) == r
    assert minimales3(xss) == r

# La comprobación es
#    >>> test_minimales_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('minimales1([range(1, n) for n in range(1, 300)])')
#    3.08 segundos
#    >>> tiempo('minimales2([range(1, n) for n in range(1, 300)])')
#    0.46 segundos
#    >>> tiempo('minimales3([range(1, n) for n in range(1, 300)])')
#    0.21 segundos
#
#    >>> tiempo('minimales2([range(1, n) for n in range(1, 500)])')
#    1.92 segundos
#    >>> tiempo('minimales3([range(1, n) for n in range(1, 500)])')
#    0.96 segundos