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
1 |
enlacesPrimos :: Int -> [[Int]] |
tal que (enlacesPrimos n) es la lista de los enlaces primos de longitud n. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 |
λ> 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
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
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) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>