Menu Close

Orden simétrico

Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera simétrica colocando la primera cadena en primer lugar, la segunda en el último, la tercera en el segundo, la cuarta en el penúltimo y así sucesivamente.

Por ejemplo, dada la lista

   Pi
   Eva
   Luis
   Paula
   Alberto
   Francisco

su ordenación simétrica es

   Pi
   Luis
   Alberto
   Francisco
   Paula
   Eva

Definir la función

   simetrica :: [String] -> [String]

tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,

   λ> simetrica ["Pi","Eva","Luis","Paula","Alberto","Francisco"]
   ["Pi","Luis","Alberto","Francisco","Paula","Eva"]
   λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^6]]
   "a"

Nota: Este ejercicio está basado en el problema Symmetric order de Kattis.

Soluciones

-- 1ª definición
simetrica1 :: [String] -> [String]
simetrica1 []       = []
simetrica1 [x]      = [x]
simetrica1 (x:y:xs) = x : simetrica1 xs ++ [y]
 
-- 2ª definición
simetrica2 :: [String] -> [String]
simetrica2 xs = aux xs []
  where aux (x:y:xs) ys = x : aux xs (y:ys)
        aux (x:xs) ys   = x : aux xs ys
        aux [] ys       = ys
 
 
-- 3ª definición
simetrica3 :: [String] -> [String]
simetrica3 xs = aux xs []
  where aux (x:y:xs) ys = x : aux xs (y:ys)
        aux xs ys       = xs ++ ys
 
-- Comparación de eficiencia
-- =========================
 
--    λ> minimum $ simetrica1 [replicate k 'a' | k <- [1..2*10^4]]
--    "a"
--    (11.30 secs, 8,600,879,688 bytes)
--    λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^4]]
--    "a"
--    (0.06 secs, 12,419,568 bytes)
--    λ> minimum $ simetrica3 [replicate k 'a' | k <- [1..2*10^4]]
--    "a"
--    (0.06 secs, 11,320,264 bytes)
Medio

25 soluciones de “Orden simétrico

  1. enrnarbej
    simetrica :: [String] -> [String]
    simetrica xs = aux 1 xs
      where
        aux _ []     = []
        aux n (x:xs) | odd n     = x : aux (n+1) xs
                     | otherwise = aux (n+1) xs ++ [x]
    • Alejandro

      La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.

  2. eliguivil
    simetrica :: [String] -> [String]
    simetrica = aux1
      where
        aux1 []     = []
        aux1 (x:xs) = x : aux2 xs
        aux2 []     = []
        aux2 (x:xs) = (aux1 xs) ++ [x]
    • Alejandro

      La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.

  3. albcercid
    import Data.List (sort)
     
    simetrica :: [String] -> [String]
    simetrica = map snd . aux . sort . map f
      where f x = (length x,x)
            aux []       = []
            aux [x]      = [x]
            aux (x:y:xs) = x : aux xs ++ [y]
    • Alejandro

      La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.

  4. marlobrip
    simetrica :: [String] -> [String]
    simetrica = reverse . aux 
       where aux (x:y:xs) = y:aux xs ++ [x]
             aux [] = []
    • José A. Alonso

      Falla si hay un número impar de elementos. Por ejemplo,

      λ> simetrica ["Pi","Eva","Luis","Paula","Alberto"] 
      *** Exception: Non-exhaustive patterns in function aux

      Se puede corregir añadiendo una ecuación para las listas unitarias.

    • marlobrip
      simetrica :: [String] -> [String]
      simetrica = reverse . aux 
         where aux (x:y:xs) = y:aux xs ++ [x]
               aux [x] = [x]
               aux [] = []
  5. josejuan

    A vuelapluma con coste lineal

    simetrica = a [] where
      a ys [] = reverse ys
      a ys (x:xs) = x: b ys xs
      b ys [] = reverse ys
      b ys (x:xs) = a (x:ys) xs
    • Alejandro

      Falla en el primer ejemplo.

      λ> simetricaA4 ["Pi","Eva","Luis","Paula","Alberto","Francisco"] 
      ["Pi","Luis","Alberto","Eva","Paula","Francisco"]

      Se puede corregir eliminando el primer reverse.

      • josejuan

        Realmente no, es eliminando los dos reverses (la cola ya se genera invertida).

    • josejuan

      La anterior es adecuada, pero tras algunas rotaciones obtenemos ésta divertida ofuscación xD

      simetrica = flip (a (const$(:).head) (.tail)) [] where
        a _ _ [] = id
        a u v xs = u (a u v) xs . v (a v u) xs
  6. josejuan

    A vuelapluma O(n log n) (y graves errores de precision para n grande)

    simetrica = map snd . sort . zipWith (i e -> (i*cos(i*pi)*exp (i*cos(i*pi)),e)) [0,1..]
      • josejuan

        Efectivamente, no se que estaba pensando. Con la siguiente debería rular (aqui no puedo probar)

        i e -> (2*fromIntegral(length xs)+(1+cos(i*pi))*exp(-i),e)
        • josejuan

          Nada, mejor usar racionales:

          import Data.List (sort)
          import Data.Ratio
           
          simetrica xs = map snd $ sort $ zipWith ((,) . index) [0..] xs
            where index i = if even i then i % 1 else length xs % 1 + 1 % i
           
          -- usando reales
          --  where index i = (1+cos(i*pi)) * i + (1+cos((i+1)*pi)) * (2*fromIntegral(length xs)+exp(-i))
  7. josejuan

    Esta también con coste lineal

    simetrica = a [] where
      a r (x:y:z) = x: a (y:r) z
      a r      z  = reverse$ z ++ r
    • josejuan

      Otra vez el reverse xD

      simetrica = a [] where
        a r (x:y:z) = x: a (y:r) z
        a r      z  = z ++ r
  8. natalia
    simetrica :: [String]->[String]
    simetrica [] = []
    simetrica [xs]= [xs]
    simetrica (xs:ps:xss)= reverse(ps:(reverse(xs:(simetrica xss))))
  9. fraferpoy
    simetrica :: [String] -> [String]
    simetrica [] = []
    simetrica (x:y:xs) = x:simetrica xs ++ [y]
    • fraferpoy
      simetrica :: [String] -> [String]
      simetrica [] = []
      simetrica [x] = [x]
      simetrica (x:y:xs) = x:simetrica xs ++ [y]
  10. glovizcas
    simetrica :: [String] -> [String]
    simetrica []       = []
    simetrica [x]      = [x]
    simetrica (x:y:xs) = [x] ++ simetrica xs ++ [y]
  11. alvfercen
    simetrica :: [String] -> [String]
    simetrica []       = []
    simetrica [x]      = [x]
    simetrica (x:y:ys) = x : simetrica ys ++ [y]
  12. Juanjo Ortega (juaorture)
     
    -- Primera definición (poco eficiente)
    simetrica :: [String] -> [String]
    simetrica (x:y:xs) = x : simetrica xs ++ [y]
    simetrica xs       = xs
     
    -- Segunda definición, bastante más eficiente
    simetrica2 :: [String] -> [String]
    simetrica2 = aux 0 []
              where aux _ ys  []    = ys
                    aux n ys (x:xs) | even n = x : aux (n+1) ys xs
                                    | otherwise = aux (n+1) (x:ys) xs
     
    -- En la última definición se elimina el parámetro que determina la acción de la función creando dos funciones.
    -- Aumenta la eficiencia.
    simetrica3 :: [String] -> [String]
    simetrica3 = aux1 []
              where aux1 ys  []    = ys
                    aux1 ys (x:xs) = x : aux2 ys xs
                    aux2 ys  []    = ys
                    aux2 ys (x:xs) = aux1 (x:ys) xs

Escribe tu solución

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