Enlaces primos
Un enlace primo de longitud n es una permutación de 1, 2, ..., n comienza con 1 y termina con n, tal que la suma de cada par de términos adyacentes es primo. Por ejemplo, para n = 6 la lista [1,4,3,2,5,6] es un enlace primo ua que las sumas de los pares de términos adyacentes son los números primos 5, 7, 5, 7, 11.
Definir la función
enlacesPrimos :: Int -> [[Int]]
tal que (enlacesPrimos n) es la lista de los enlaces primos de longitud n. Por ejemplo,
λ> enlacesPrimos 6 [[1,4,3,2,5,6]] λ> enlacesPrimos 7 [[1,4,3,2,5,6,7],[1,6,5,2,3,4,7]] λ> enlacesPrimos 8 [[1,2,5,6,7,4,3,8],[1,4,7,6,5,2,3,8],[1,2,3,4,7,6,5,8],[1,6,7,4,3,2,5,8]] λ> length (enlacesPrimos 10) 24 λ> length (head (enlacesPrimos (5*10^4))) 50000
Soluciones
import Data.List (permutations, delete) import Data.Numbers.Primes (isPrime) -- 1ª solución -- =========== enlacesPrimos :: Int -> [[Int]] enlacesPrimos 1 = [[1]] enlacesPrimos n = [ys | xs <- permutations [2..n-1], let ys = (1:xs)++[n], conEnlacesPrimos ys] -- (conEnlacesPrimos xs) se verifica si las sumas de los elementos -- adyacentes de xs son primos. Por ejemplo, -- conEnlacesPrimos [1,4,3,2,5,6] == True -- conEnlacesPrimos [1,3,4,2,5,6] == False conEnlacesPrimos :: [Int] -> Bool conEnlacesPrimos xs = all isPrime (enlaces xs) -- (enlaces xs) es la lista de las sumas de los elementos adyacentes de -- xs. Por ejemplo, -- enlaces [1,4,3,2,5,6] == [5,7,5,7,11] -- enlaces [1,3,4,2,5,6] == [4,7,6,7,11] enlaces :: [Int] -> [Int] enlaces xs = zipWith (+) xs (tail xs) -- 2ª solución -- =========== enlacesPrimos2 :: Int -> [[Int]] enlacesPrimos2 1 = [[1]] enlacesPrimos2 n = aux [(n-1,[n],[n-1,n-2..2])] where aux [] = [] aux ((1,x:xs,_):ts) = [1:x:xs | isPrime (1+x)] ++ aux ts aux ((k,x:xs,ys):ts) = aux ([(k-1,y:x:xs,delete y ys) | y <-ys, isPrime (y+x)] ++ ts) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (enlacesPrimos 12) -- 216 -- (6.04 secs, 22,266,444,408 bytes) -- λ> length (enlacesPrimos2 12) -- 216 -- (0.03 secs, 18,102,192 bytes) -- -- λ> length (enlacesPrimos2 17) -- 59448 -- (2.69 secs, 8,514,104,800 bytes)