Número de emparejamientos de amigos
El problema del número de emparejamiento de amigos consiste en calcular el número de formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos son
{1}, {2}, {3}
{1}, {2, 3}
{1, 2}, {3}
{1, 3}, {2}
Definir la función
nEmparejamientos :: Integer -> Integer
tal que (nEmparejamientos n) es el número de formas de emparejar a los n amigos. Por ejemplo,
nEmparejamientos 2 == 2 nEmparejamientos 3 == 4 nEmparejamientos 4 == 10 nEmparejamientos 10 == 9496 nEmparejamientos 30 == 606917269909048576 length (show (nEmparejamientos3 (10^4))) == 17872
Soluciones
import Data.List (delete, genericLength) import Data.Array -- 1ª solución -- =========== nEmparejamientos :: Integer -> Integer nEmparejamientos = genericLength . emparejamientos emparejamientos :: Integer -> [[[Integer]]] emparejamientos n = aux [1..n] where aux [] = [[]] aux (x:xs) = [[x] : ps | ps <- aux xs] ++ [[x,y] : ps | y <- xs, ps <- aux (delete y xs)] -- 2ª solución -- =========== nEmparejamientos2 :: Integer -> Integer nEmparejamientos2 0 = 1 nEmparejamientos2 1 = 1 nEmparejamientos2 2 = 2 nEmparejamientos2 n = nEmparejamientos2 (n - 1) + (n - 1) * nEmparejamientos2 (n - 2) -- 3ª solución -- =========== nEmparejamientos3 :: Integer -> Integer nEmparejamientos3 n = (vectorEmparejamientos n) ! n -- (vectorEmparejamientos n) es el vector con índices de 0 a n tal que el valor -- de la posición i es el número de formas de emparejar a i amigos. Por ejemplo, -- λ> vectorEmparejamientos 7 -- array (0,7) [(0,1),(1,1),(2,2),(3,4),(4,10),(5,26),(6,76),(7,232)] vectorEmparejamientos :: Integer -> Array Integer Integer vectorEmparejamientos n = v where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 1 f 1 = 1 f 2 = 2 f n = v!(n-1) + (n-1)*v!(n-2) -- Comparación de eficiencia -- ========================= -- λ> nEmparejamientos 12 -- 140152 -- (1.81 secs, 280,218,616 bytes) -- λ> nEmparejamientos2 12 -- 140152 -- (0.01 secs, 177,168 bytes) -- λ> nEmparejamientos3 12 -- 140152 -- (0.01 secs, 108,816 bytes) -- -- λ> nEmparejamientos2 30 -- 606917269909048576 -- (3.97 secs, 449,224,280 bytes) -- λ> nEmparejamientos3 30 -- 606917269909048576 -- (0.01 secs, 135,160 bytes)