Ordenada cíclicamente

Enunciado

-- Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente
-- si existe un índice i tal que la sucesión  
--    x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)
-- está ordenada crecientemente. 
-- 
-- Definir la función 
--    ordenadaCiclicamente :: Ord a => [a] -> Int
-- tal que (ordenadaCiclicamente xs) es el índice (empezando en 1) a
-- partir del cual está ordenada, si el la lista está ordenado cíclicamente
-- y 0 en caso contrario. Por ejemplo,
--    ordenadaCiclicamente [1,2,3,4]      ==  1  
--    ordenadaCiclicamente [5,8,2,3]      ==  3 
--    ordenadaCiclicamente [4,6,7,5,4,3]  ==  0 
--    ordenadaCiclicamente [1,0,1,2]      ==  0
--    ordenadaCiclicamente [0,2,0]        ==  3
--    ordenadaCiclicamente "cdeab"        ==  4

-- Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente

-- si existe un índice i tal que la sucesión

-- x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)

-- está ordenada crecientemente.

-- Definir la función

-- ordenadaCiclicamente :: Ord a => [a] -> Int

-- tal que (ordenadaCiclicamente xs) es el índice (empezando en 1) a

-- partir del cual está ordenada, si el la lista está ordenado cíclicamente

-- y 0 en caso contrario. Por ejemplo,

-- ordenadaCiclicamente [1,2,3,4] == 1

-- ordenadaCiclicamente [5,8,2,3] == 3

-- ordenadaCiclicamente [4,6,7,5,4,3] == 0

-- ordenadaCiclicamente [1,0,1,2] == 0

-- ordenadaCiclicamente [0,2,0] == 3

-- ordenadaCiclicamente "cdeab" == 4

Soluciones

-- 1ª definición (por comprensión)
-- ===============================

ordenadaCiclicamente1 :: Ord a => [a] -> Int
ordenadaCiclicamente1 xs = 
    primero [n+1 | n <- [0..length xs-1], 
                   ordenada (drop n xs ++ take n xs)]
    where primero []     = 0
          primero (x:xs) = x

-- (ordenada xs) se verifica si la lista xs está ordenada
-- crecientemente. Por ejemplo,
--   ordenada "acd"   ==  True
--   ordenada "acdb"  ==  False
ordenada :: Ord a => [a] -> Bool 
ordenada (x:y:zs) = x <= y && ordenada (y:zs) 
ordenada _        = True 
 
-- 2ª definición (por recursión)
-- =============================

ordenadaCiclicamente2 :: Ord a => [a] -> Int
ordenadaCiclicamente2 xs = aux xs 1 (length xs)  
    where aux xs i k 
              | i > k       = 0 
              | ordenada xs = i 
              | otherwise   = aux (siguienteCiclo xs) (i+1) k 

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento
-- de xs al final del resto de xs. Por ejemplo,
--   siguienteCiclo [3,2,5]  =>  [2,5,3]
siguienteCiclo [] = [] 
siguienteCiclo (x:xs) = xs ++ [x]

-- 1ª definición (por comprensión)

-- ===============================

ordenadaCiclicamente1 :: Ord a => [a] -> Int

ordenadaCiclicamente1 xs =

primero [n+1 | n <- [0..length xs-1],

ordenada (drop n xs ++ take n xs)]

where primero [] = 0

primero (x:xs) = x

-- (ordenada xs) se verifica si la lista xs está ordenada

-- crecientemente. Por ejemplo,

-- ordenada "acd" == True

-- ordenada "acdb" == False

ordenada :: Ord a => [a] -> Bool

ordenada (x:y:zs) = x <= y && ordenada (y:zs)

ordenada _ = True

-- 2ª definición (por recursión)

-- =============================

ordenadaCiclicamente2 :: Ord a => [a] -> Int

ordenadaCiclicamente2 xs = aux xs 1 (length xs)

where aux xs i k

| i > k = 0

| ordenada xs = i

| otherwise = aux (siguienteCiclo xs) (i+1) k

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento

-- de xs al final del resto de xs. Por ejemplo,

-- siguienteCiclo [3,2,5] => [2,5,3]

siguienteCiclo [] = []

siguienteCiclo (x:xs) = xs ++ [x]

3 Comentarios

ordenadaCiclicamente xs = 
    if   (ordenadaCiclicamente1 (length xs) xs) <= (length xs)  
    then ordenadaCiclicamente1 (length xs) xs 
    else 0

ordenadaCiclicamente1 0 xs = length xs
ordenadaCiclicamente1 n ys@(x:xs) 
    | ordenada ys = 1
    | otherwise   = 1 + ordenadaCiclicamente1 (n-1) (xs ++ [x])

ordenada [x] = True
ordenada (x:y:xs) | x <= y    = ordenada (y:xs)
                  | otherwise = False

ordenadaCiclicamente xs =

if (ordenadaCiclicamente1 (length xs) xs) <= (length xs)

then ordenadaCiclicamente1 (length xs) xs

else 0

ordenadaCiclicamente1 0 xs = length xs

ordenadaCiclicamente1 n ys@(x:xs)

| ordenada ys = 1

| otherwise = 1 + ordenadaCiclicamente1 (n-1) (xs ++ [x])

ordenada [x] = True

ordenada (x:y:xs) | x <= y = ordenada (y:xs)

| otherwise = False

Responder

ordenadaCiclicamente :: Ord a => [a] -> Int
ordenadaCiclicamente xs
    | or ys     = length (takeWhile (==False) ys) + 1
    | otherwise = 0
    where ys = [reordena n xs == sort xs | n <- [1..length xs]]

reordena n xs = drop (n-1) xs ++ take (n-1) xs

ordenadaCiclicamente :: Ord a => [a] -> Int

ordenadaCiclicamente xs

| or ys = length (takeWhile (==False) ys) + 1

| otherwise = 0

where ys = [reordena n xs == sort xs | n <- [1..length xs]]

reordena n xs = drop (n-1) xs ++ take (n-1) xs

import Data.List

ordenadaCiclicamente :: Ord a => [a] -> Int
ordenadaCiclicamente xs = ordenada 1 xs

ordenada :: Ord a => Int -> [a] -> Int
ordenada n (x:xs) | n > length (x:xs) = 0
                  | sort (x:xs) == (x:xs) = n
                  | otherwise = ordenada (n+1) (xs++[x])

import Data.List

ordenadaCiclicamente xs = ordenada 1 xs

ordenada :: Ord a => Int -> [a] -> Int

ordenada n (x:xs) | n > length (x:xs) = 0

| sort (x:xs) == (x:xs) = n

| otherwise = ordenada (n+1) (xs++[x])

Ordenada cíclicamente

Enunciado

Soluciones

3 Comentarios

Leave a Reply to Paco JácomeCancel reply

Entradas recientes

Buscar

Correo electrónico

Enunciado

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to Paco JácomeCancel reply

Entradas recientes

Buscar

Correo electrónico