Permutación cíclica
Definir la función
1 |
ciclo :: [a] -> [a] |
tal que (ciclo xs)
es la lista obtenida permutando cíclicamente los elementos de la lista xs
, pasando el último elemento al principio de la lista. Por ejemplo,
1 2 3 |
ciclo [2,5,7,9] == [9,2,5,7] ciclo [] == [] ciclo [2] == [2] |
Comprobar que la longitud es un invariante de la función ciclo; es decir, la longitud de (ciclo xs)
es la misma que la de xs
.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
import Test.QuickCheck ciclo :: [a] -> [a] ciclo [] = [] ciclo xs = last xs : init xs -- La propiedad es prop_ciclo :: [Int] -> Bool prop_ciclo xs = length (ciclo xs) == length xs -- La comprobación es -- λ> quickCheck prop_ciclo -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
from typing import TypeVar from hypothesis import given, strategies as st A = TypeVar('A') def ciclo(xs: list[A]) -> list[A]: if xs: return [xs[-1]] + xs[:-1] return [] # La propiedad de es @given(st.lists(st.integers())) def test_equiv_ciclo(xs): assert len(ciclo(xs)) == len(xs) # La comprobación es # src> poetry run pytest -q permutacion_ciclica.py # 1 passed in 0.39s |
El código se encuentra en GitHub.