Agrupación de elementos por posición
Definir la función
|
1 |
agrupa :: Eq a => [[a]] -> [[a]] |
tal que agrupa xsses la lista de las listas obtenidas agrupando los primeros elementos, los segundos, … Por ejemplo,
|
1 |
agrupa [[1..6],[7..9],[10..20]] == [[1,7,10],[2,8,11],[3,9,12]] |
Comprobar con QuickChek que la longitud de todos los elementos de agrupa xs es igual a la longitud de xs.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
import Data.List (transpose) import qualified Data.Matrix as M (fromLists, toLists, transpose) import Test.QuickCheck -- 1ª solución -- =========== -- (primeros xss) es la lista de los primeros elementos de xss. Por -- ejemplo, -- primeros [[1..6],[7..9],[10..20]] == [1,7,10] primeros :: [[a]] -> [a] primeros = map head -- (restos xss) es la lista de los restos de elementos de xss. Por -- ejemplo, -- restos [[1..3],[7,8],[4..7]] == [[2,3],[8],[5,6,7]] restos :: [[a]] -> [[a]] restos = map tail agrupa1 :: Eq a => [[a]] -> [[a]] agrupa1 [] = [] agrupa1 xss | [] `elem` xss = [] | otherwise = primeros xss : agrupa1 (restos xss) -- 2ª solución -- =========== -- (conIgualLongitud xss) es la lista obtenida recortando los elementos -- de xss para que todos tengan la misma longitud. Por ejemplo, -- > conIgualLongitud [[1..6],[7..9],[10..20]] -- [[1,2,3],[7,8,9],[10,11,12]] conIgualLongitud :: [[a]] -> [[a]] conIgualLongitud xss = map (take n) xss where n = minimum (map length xss) agrupa2 :: Eq a => [[a]] -> [[a]] agrupa2 = transpose . conIgualLongitud -- 3ª solución -- =========== agrupa3 :: Eq a => [[a]] -> [[a]] agrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_agrupa :: NonEmptyList [Int] -> Bool prop_agrupa (NonEmpty xss) = all (== agrupa1 xss) [agrupa2 xss, agrupa3 xss] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (agrupa1 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (3.96 secs, 16,012,109,904 bytes) -- λ> length (agrupa2 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (25.80 secs, 19,906,197,528 bytes) -- λ> length (agrupa3 [[1..10^4] | _ <- [1..10^4]]) -- 10000 -- (9.56 secs, 7,213,797,984 bytes) -- La comprobación es -- λ> quickCheck prop_agrupa -- +++ OK, passed 100 tests. -- La propiedad es prop_agrupa_length :: [[Int]] -> Bool prop_agrupa_length xss = and [length xs == n | xs <- agrupa1 xss] where n = length xss -- La comprobación es -- λ> quickCheck prop_agrupa_length -- +++ OK, passed 100 tests. |
|
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from numpy import transpose, array setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== # primeros(xss) es la lista de los primeros elementos de xss. Por # ejemplo, # primeros([[1,6],[7,8,9],[3,4,5]]) == [1, 7, 3] def primeros(xss: list[list[A]]) -> list[A]: return [xs[0] for xs in xss] # restos(xss) es la lista de los restos de elementos de xss. Por # ejemplo, # >>> restos([[1,6],[7,8,9],[3,4,5]]) # [[6], [8, 9], [4, 5]] def restos(xss: list[list[A]]) -> list[list[A]]: return [xs[1:] for xs in xss] def agrupa1(xss: list[list[A]]) -> list[list[A]]: if not xss: return [] if [] in xss: return [] return [primeros(xss)] + agrupa1(restos(xss)) # 2ª solución # =========== # conIgualLongitud(xss) es la lista obtenida recortando los elementos # de xss para que todos tengan la misma longitud. Por ejemplo, # >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]]) # [[1, 6], [7, 8], [3, 4]] def conIgualLongitud(xss: list[list[A]]) -> list[list[A]]: n = min(map(len, xss)) return [xs[:n] for xs in xss] def agrupa2(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return [[ys[i] for ys in yss] for i in range(len(yss[0]))] # 3ª solución # =========== def agrupa3(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return list(map(list, zip(*yss))) # 4ª solución # =========== def agrupa4(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) return (transpose(array(yss))).tolist() # 5ª solución # =========== def agrupa5(xss: list[list[A]]) -> list[list[A]]: yss = conIgualLongitud(xss) r = [] for i in range(len(yss[0])): f = [] for xs in xss: f.append(xs[i]) r.append(f) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_agrupa(xss: list[list[int]]) -> None: r = agrupa1(xss) assert agrupa2(xss) == r assert agrupa3(xss) == r assert agrupa4(xss) == r assert agrupa5(xss) == r # La comprobación es # src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py # 1 passed in 0.74s # 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('agrupa1([list(range(10**3)) for _ in range(10**3)])') # 4.44 segundos # >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])') # 0.10 segundos # >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])') # 0.10 segundos # >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])') # 0.12 segundos # >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])') # 0.15 segundos # # >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])') # 21.25 segundos # >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])') # 20.82 segundos # >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])') # 13.46 segundos # >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])') # 21.70 segundos # La propiedad es @given(st.lists(st.lists(st.integers()), min_size=1)) def test_agrupa_length(xss: list[list[int]]) -> None: n = len(xss) assert all((len(xs) == n for xs in agrupa2(xss))) # La comprobación es # src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py # 2 passed in 1.25s |