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

su ordenación simétrica es

Definir la función

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

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

Soluciones

25 Comentarios

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

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

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

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

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

  1. A vuelapluma con coste lineal

    1. Falla en el primer ejemplo.

      Se puede corregir eliminando el primer reverse.

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

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

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

        1. Nada, mejor usar racionales:

  3. Esta también con coste lineal

    1. Otra vez el reverse xD

Leave a Reply to fraferpoyCancel reply