Ordenación por el máximo

José A. Alonso

29-01-2025

Definir la función

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

tal que (ordenadosPorMaximo xss) es la lista de los elementos de xss ordenada por sus máximos (se supone que los elementos de xss son listas no vacía) y cuando tiene el mismo máximo se conserva el orden original. Por ejemplo,

λ> ordenadosPorMaximo [[0,8],[9],[8,1],[6,3],[8,2],[6,1],[6,2]]
[[6,3],[6,1],[6,2],[0,8],[8,1],[8,2],[9]]
λ> ordenadosPorMaximo ["este","es","el","primero"]
["el","primero","es","este"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Soluciones

A continuación se muestran

las soluciones en Haskell,
las soluciones en Python y
las soluciones en Common Lisp

1. Soluciones en Haskell

module Ordenados_por_maximo where

import Data.List (sort, sortBy)
import GHC.Exts (sortWith)
import Data.Map (elems, fromList)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

ordenadosPorMaximo1 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo1 xss =
  map snd (sort [((maximum xs,k),xs) | (k,xs) <- zip [0..] xss])

-- 2ª solución
-- ===========

ordenadosPorMaximo2 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo2 xss =
  [xs | (_,xs) <- sort [((maximum xs,k),xs) | (k,xs) <- zip [0..] xss]]

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

ordenadosPorMaximo3 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo3 =
  sortBy (\xs ys -> compare (maximum xs) (maximum ys))

-- 4ª solución
-- ===========

ordenadosPorMaximo4 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo4 = sortWith maximum

-- 5ª solución
-- ===========

ordenadosPorMaximo5 :: Ord a => [[a]] -> [[a]]
ordenadosPorMaximo5 xss =
  elems (fromList [((maximum xs, k), xs) | (k, xs) <- zip [0..] xss])

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

verifica :: IO ()
verifica = hspec spec

specG :: ([[Int]] -> [[Int]]) -> Spec
specG ordenadosPorMaximo = do
  it "e1" $
    ordenadosPorMaximo [[0,8],[9],[8,1],[6,3],[8,2],[6,1],[6,2]] `shouldBe`
      [[6,3],[6,1],[6,2],[0,8],[8,1],[8,2],[9]]

spec :: Spec
spec = do
  describe "def. 1" $ specG ordenadosPorMaximo1
  describe "def. 2" $ specG ordenadosPorMaximo2
  describe "def. 3" $ specG ordenadosPorMaximo3
  describe "def. 4" $ specG ordenadosPorMaximo4
  describe "def. 5" $ specG ordenadosPorMaximo5

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

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

-- La propiedad es
prop_ordenadosPorMaximo :: [[Int]] -> Bool
prop_ordenadosPorMaximo xss =
  all (== ordenadosPorMaximo1 yss)
      [ordenadosPorMaximo2 yss,
       ordenadosPorMaximo3 yss,
       ordenadosPorMaximo4 yss,
       ordenadosPorMaximo5 yss]
  where yss = filter (not . null) xss

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

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

-- La comparación es
--    λ> length (ordenadosPorMaximo1 [[1..k] | k <- [1..10^4]])
--    10000
--    (6.00 secs, 8,763,714,848 bytes)
--    λ> length (ordenadosPorMaximo2 [[1..k] | k <- [1..10^4]])
--    10000
--    (6.15 secs, 8,764,177,472 bytes)
--    λ> length (ordenadosPorMaximo3 [[1..k] | k <- [1..10^4]])
--    10000
--    (8.16 secs, 13,914,503,672 bytes)
--    λ> length (ordenadosPorMaximo4 [[1..k] | k <- [1..10^4]])
--    10000
--    (7.77 secs, 13,914,183,776 bytes)
--    λ> length (ordenadosPorMaximo5 [[1..k] | k <- [1..10^4]])
--    10000
--    (6.71 secs, 3,607,840,248 bytes)

2. Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def ordenadosPorMaximo1(xss: list[list[int]]) -> list[list[int]]:
    return [xs for _, _, xs in sorted(((max(xs), k, xs) for k, xs in enumerate(xss)))]

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

def ordenadosPorMaximo2(xss: list[list[int]]) -> list[list[int]]:
    return sorted(xss, key=max)

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

def test_ordenadosPorMaximo() -> None:
    for ordenadosPorMaximo in [ordenadosPorMaximo1, ordenadosPorMaximo2]:
        assert ordenadosPorMaximo([[0,8],[9],[8,1],[6,3],[8,2],[6,1],[6,2]]) ==\
            [[6,3],[6,1],[6,2],[0,8],[8,1],[8,2],[9]]
        print(f"Verificado {ordenadosPorMaximo.__name__}")

# La verificación es
#    >>> test_ordenadosPorMaximo()
#    Verificado ordenadosPorMaximo1
#    Verificado ordenadosPorMaximo2

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

# La propiedad es
@given(st.lists(st.lists(st.integers(), min_size=1)))
def test_ordenadosPorMaximo_equiv(xss: list[list[int]]) -> None:
    assert ordenadosPorMaximo1(xss) == ordenadosPorMaximo2(xss)

# La comprobación es
#    >>> test_ordenadosPorMaximo_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('ordenadosPorMaximo1([[i for i in range(k)] for k in range(1, 10**4)])')
#    2.87 segundos
#    >>> tiempo('ordenadosPorMaximo2([[i for i in range(k)] for k in range(1, 10**4)])')
#    2.86 segundos

2. Soluciones en Common Lisp

(ql:quickload "fiveam" :silent t)

(defpackage :ordenados-por-maximo
  (:use :cl
        :fiveam))

(in-package :ordenados-por-maximo)

;;; 1ª solución
;;; ===========

(defun ordenados-por-maximo1 (xss)
  (mapcar #'rest
          (sort (loop for xs in xss
                      for k from 0
                      collect (cons (cons (apply #'max xs) k) xs))
                #'<
                :key #'(lambda (pair) (first (first pair))))))

;;; 2ª solución
;;; ===========

;;; (maximo xs) el máximo elemento de la lista no vacía xs. Por ejemplo,
;;;    > (maximo '(3 7 2))
;;;    7
(defun maximo (xs)
  (reduce #'max xs))

(defun ordenados-por-maximo2 (xss)
  (stable-sort (copy-seq xss)
               #'(lambda (xs ys) (< (maximo xs) (maximo ys)))))

;;; 3ª solución
;;; ===========

(defun ordenados-por-maximo3 (xss)
  (stable-sort (copy-seq xss)
               #'< :key (lambda (xs) (reduce #'max xs))))

;;; 4ª solución
;;; ===========

(defun ordenados-por-maximo4 (xss)
  (let* ((con-maximos (mapcar (lambda (xs) (cons xs (maximo xs))) xss))
         (ordenados (sort con-maximos #'< :key #'cdr)))
    (mapcar #'car ordenados)))

;;; Verificación
;;; ============

(test ordenados-por-maximo
  (is (equal (ordenados-por-maximo1 '((0 8) (9) (8 1) (6 3) (8 2) (6 1) (6 2)))
             '((6 3) (6 1) (6 2) (0 8) (8 1) (8 2) (9))))
  (is (equal (ordenados-por-maximo2 '((0 8) (9) (8 1) (6 3) (8 2) (6 1) (6 2)))
             '((6 3) (6 1) (6 2) (0 8) (8 1) (8 2) (9))))
  (is (equal (ordenados-por-maximo3 '((0 8) (9) (8 1) (6 3) (8 2) (6 1) (6 2)))
             '((6 3) (6 1) (6 2) (0 8) (8 1) (8 2) (9))))
  (is (equal (ordenados-por-maximo4 '((0 8) (9) (8 1) (6 3) (8 2) (6 1) (6 2)))
             '((6 3) (6 1) (6 2) (0 8) (8 1) (8 2) (9))))
  )

(defun verifica ()
  (run 'ordenados-por-maximo))

;;; La verificación es
;;;    CL-USER> (ordenados-por-maximo::verifica)
;;;
;;;    Running test ORDENADOS-POR-MAXIMO ....

;;; Equivalencia de las definiciones
;;; ================================

;;; La propiedad es
(test ordenados-por-maximo-equiv
  (for-all ((xss (gen-list
                 :elements (gen-list
                            :elements (gen-integer)))))
    (let* ((yss (remove-if #'null xss))
           (r (ordenados-por-maximo1 yss)))
      (is (equal r (ordenados-por-maximo2 yss)))
      (is (equal r (ordenados-por-maximo2 yss)))
      (is (equal r (ordenados-por-maximo3 yss)))
      )))

(defun comprueba ()
  (run 'ordenados-por-maximo-equiv))

;;; La comprobación es
;;;    > (ordenados-por-maximo::comprueba)
;;;
;;;    Running test ORDENADOS-POR-MAXIMO-EQUIV ...
;;;    (#<IT.BESE.FIVEAM::FOR-ALL-TEST-PASSED {1003EDAF13}>)

;;; Comparación de eficiencia
;;; =========================

;;; (ejemplo n) es una lista con n elementos tal que su k-ésimo
;;; elementos son los números del 1 al k. Por ejemplo,
;;;    > (ejemplo 5)
;;;    ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))
(defun ejemplo (n)
  (loop for k from 1 to n
        collect (loop for i from 1 to k
                      collect i)))

;;; La comparación es
;;;    > (time (length (ordenados-por-maximo1 (ejemplo 6000))))
;;;    0.807 seconds of real time
;;;    > (time (length (ordenados-por-maximo2 (ejemplo 6000))))
;;;    0.739 seconds of real time
;;;    > (time (length (ordenados-por-maximo3 (ejemplo 6000))))
;;;    0.821 seconds of real time
;;;    > (time (length (ordenados-por-maximo4 (ejemplo 6000))))
;;;    0.738 seconds of real time