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
1 2 3 4 5 6 |
Pi Eva Luis Paula Alberto Francisco |
su ordenación simétrica es
1 2 3 4 5 6 |
Pi Luis Alberto Francisco Paula Eva |
Definir la función
1 |
simetrica :: [String] -> [String] |
tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,
1 2 3 4 |
λ> 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 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 |
-- 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) |
La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.
La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.
La complejidad es cuadrática y se puede definir con complejidad lineal evitando el añadir por el final de la lista.
Falla si hay un número impar de elementos. Por ejemplo,
Se puede corregir añadiendo una ecuación para las listas unitarias.
A vuelapluma con coste lineal
Falla en el primer ejemplo.
Se puede corregir eliminando el primer reverse.
Realmente no, es eliminando los dos reverses (la cola ya se genera invertida).
La anterior es adecuada, pero tras algunas rotaciones obtenemos ésta divertida ofuscación xD
A vuelapluma O(n log n) (y graves errores de precision para n grande)
Falla en el primer ejemplo.
Efectivamente, no se que estaba pensando. Con la siguiente debería rular (aqui no puedo probar)
Nada, mejor usar racionales:
Esta también con coste lineal
Otra vez el reverse xD