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 4 |
{1}, {2}, {3} {1}, {2, 3} {1, 2}, {3} {1, 3}, {2} |
Definir la función
1 |
nEmparejamientos :: Integer -> Integer |
tal que (nEmparejamientos n) es el número de formas de emparejar a los n amigos. Por ejemplo,
1 2 3 4 5 6 |
nEmparejamientos 2 == 2 nEmparejamientos 3 == 4 nEmparejamientos 4 == 10 nEmparejamientos 10 == 9496 nEmparejamientos 30 == 606917269909048576 length (show (nEmparejamientos3 (10^4))) == 17872 |
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 57 58 59 60 61 |
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) |
Pensamiento
Toda la imaginería
que no ha brotado del río,
barata bisutería.Antonio Machado
Se propone la solución trivial usando lo de ayer y una segunda.