{"id":7519,"date":"2022-11-17T09:09:12","date_gmt":"2022-11-17T07:09:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7519"},"modified":"2022-12-14T11:41:00","modified_gmt":"2022-12-14T09:41:00","slug":"17-nov-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/17-nov-22\/","title":{"rendered":"Agrupaci\u00f3n de elementos por posici\u00f3n"},"content":{"rendered":"

Definir la funci\u00f3n<\/p>\n

\n   agrupa :: Eq a => [[a]] -> [[a]]\n<\/pre>\n
tal que agrupa xss<\/code>es la lista de las listas obtenidas agrupando los primeros elementos, los segundos, … Por ejemplo,<\/p>\n
\n   agrupa [[1..6],[7..9],[10..20]]  ==  [[1,7,10],[2,8,11],[3,9,12]]\n<\/pre>\n
Comprobar con QuickChek que la longitud de todos los elementos de agrupa xs<\/code> es igual a la longitud de xs<\/code>.<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport Data.List (transpose)\nimport qualified Data.Matrix as M (fromLists, toLists, transpose)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- (primeros xss) es la lista de los primeros elementos de xss. Por\n-- ejemplo,\n--    primeros [[1..6],[7..9],[10..20]]  ==  [1,7,10]\nprimeros :: [[a]] -> [a]\nprimeros = map head\n\n-- (restos xss) es la lista de los restos de elementos de xss. Por\n-- ejemplo,\n--    restos [[1..3],[7,8],[4..7]]  ==  [[2,3],[8],[5,6,7]]\nrestos :: [[a]] -> [[a]]\nrestos = map tail\n\nagrupa1 :: Eq a => [[a]] -> [[a]]\nagrupa1 []  = []\nagrupa1 xss\n  | [] `elem` xss = []\n  | otherwise     = primeros xss : agrupa1 (restos xss)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- (conIgualLongitud xss) es la lista obtenida recortando los elementos\n-- de xss para que todos tengan la misma longitud. Por ejemplo,\n--    > conIgualLongitud [[1..6],[7..9],[10..20]]\n--    [[1,2,3],[7,8,9],[10,11,12]]\nconIgualLongitud :: [[a]] -> [[a]]\nconIgualLongitud xss = map (take n) xss\n  where n = minimum (map length xss)\n\nagrupa2 :: Eq a => [[a]] -> [[a]]\nagrupa2 = transpose . conIgualLongitud\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nagrupa3 :: Eq a => [[a]] -> [[a]]\nagrupa3 = M.toLists . M.transpose . M.fromLists . conIgualLongitud\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_agrupa :: NonEmptyList [Int] -> Bool\nprop_agrupa (NonEmpty xss) =\n  all (== agrupa1 xss)\n      [agrupa2 xss,\n       agrupa3 xss]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (agrupa1 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (3.96 secs, 16,012,109,904 bytes)\n--    \u03bb> length (agrupa2 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (25.80 secs, 19,906,197,528 bytes)\n--    \u03bb> length (agrupa3 [[1..10^4] | _ <- [1..10^4]])\n--    10000\n--    (9.56 secs, 7,213,797,984 bytes)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_agrupa\n--    +++ OK, passed 100 tests.\n\n-- La propiedad es\nprop_agrupa_length :: [[Int]] -> Bool\nprop_agrupa_length xss =\n  and [length xs == n | xs <- agrupa1 xss]\n  where n = length xss\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_agrupa_length\n--    +++ OK, passed 100 tests.\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom numpy import transpose, array\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# primeros(xss) es la lista de los primeros elementos de xss. Por\n# ejemplo,\n#    primeros([[1,6],[7,8,9],[3,4,5]])  ==  [1, 7, 3]\ndef primeros(xss: list[list[A]]) -> list[A]:\n    return [xs[0] for xs in xss]\n\n# restos(xss) es la lista de los restos de elementos de xss. Por\n# ejemplo,\n#    >>> restos([[1,6],[7,8,9],[3,4,5]])\n#    [[6], [8, 9], [4, 5]]\ndef restos(xss: list[list[A]]) -> list[list[A]]:\n    return [xs[1:] for xs in xss]\n\ndef agrupa1(xss: list[list[A]]) -> list[list[A]]:\n    if not xss:\n        return []\n    if [] in xss:\n        return []\n    return [primeros(xss)] + agrupa1(restos(xss))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# conIgualLongitud(xss) es la lista obtenida recortando los elementos\n# de xss para que todos tengan la misma longitud. Por ejemplo,\n#    >>> conIgualLongitud([[1,6],[7,8,9],[3,4,5]])\n#    [[1, 6], [7, 8], [3, 4]]\ndef conIgualLongitud(xss: list[list[A]]) -> list[list[A]]:\n    n = min(map(len, xss))\n    return [xs[:n] for xs in xss]\n\ndef agrupa2(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return [[ys[i] for ys in yss] for i in range(len(yss[0]))]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa3(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return list(map(list, zip(*yss)))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa4(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    return (transpose(array(yss))).tolist()\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef agrupa5(xss: list[list[A]]) -> list[list[A]]:\n    yss = conIgualLongitud(xss)\n    r = []\n    for i in range(len(yss[0])):\n        f = []\n        for xs in xss:\n            f.append(xs[i])\n        r.append(f)\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_agrupa(xss: list[list[int]]) -> None:\n    r = agrupa1(xss)\n    assert agrupa2(xss) == r\n    assert agrupa3(xss) == r\n    assert agrupa4(xss) == r\n    assert agrupa5(xss) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py\n#    1 passed in 0.74s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('agrupa1([list(range(10**3)) for _ in range(10**3)])')\n#    4.44 segundos\n#    >>> tiempo('agrupa2([list(range(10**3)) for _ in range(10**3)])')\n#    0.10 segundos\n#    >>> tiempo('agrupa3([list(range(10**3)) for _ in range(10**3)])')\n#    0.10 segundos\n#    >>> tiempo('agrupa4([list(range(10**3)) for _ in range(10**3)])')\n#    0.12 segundos\n#    >>> tiempo('agrupa5([list(range(10**3)) for _ in range(10**3)])')\n#    0.15 segundos\n#\n#    >>> tiempo('agrupa2([list(range(10**4)) for _ in range(10**4)])')\n#    21.25 segundos\n#    >>> tiempo('agrupa3([list(range(10**4)) for _ in range(10**4)])')\n#    20.82 segundos\n#    >>> tiempo('agrupa4([list(range(10**4)) for _ in range(10**4)])')\n#    13.46 segundos\n#    >>> tiempo('agrupa5([list(range(10**4)) for _ in range(10**4)])')\n#    21.70 segundos\n\n# La propiedad es\n@given(st.lists(st.lists(st.integers()), min_size=1))\ndef test_agrupa_length(xss: list[list[int]]) -> None:\n    n = len(xss)\n    assert all((len(xs) == n for xs in agrupa2(xss)))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q agrupacion_de_elementos_por_posicion.py\n#    2 passed in 1.25s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n agrupa :: Eq a => [[a]] -> [[a]] tal que agrupa xsses la lista de las listas obtenidas agrupando los primeros elementos, los segundos, … Por ejemplo, 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7519"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7519"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7519\/revisions"}],"predecessor-version":[{"id":7646,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7519\/revisions\/7646"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7519"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7519"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7519"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}