Emparejamiento de amigos
El problema de emparejamiento de amigos consiste en calcular las 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 |
emparejamientos :: Integer -> [[[Integer]]] |
tal que (emparejamientos n) es la lista de los posibles emparejamientos de los n amigos (numerados del 1 al n). Por ejemplo,
1 2 3 4 |
λ> emparejamientos 2 [[[1],[2]],[[1,2]]] λ> emparejamientos 3 [[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,3],[2]]] |
Soluciones
1 2 3 4 5 6 7 |
import Data.List (delete) 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)] |
Pensamiento
Crea el alma sus riberas;
montes de ceniza y plomo,
sotillos de primavera.Antonio Machado