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)