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}
{1}, {2, 3}
{1, 2}, {3}
{1, 3}, {2}
Definir la función
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,
λ> emparejamientos [1..2] [[[1],[2]],[[1,2]]] λ> emparejamientos [1..3] [[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,3],[2]]]
Soluciones
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)]