Particiones en k subconjuntos
Definir la función
particiones :: [a] -> Int -> [[[a]]]
tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,
λ> particiones [2,3,6] 2 [[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]] λ> particiones [2,3,6] 3 [[[2],[3],[6]]] λ> particiones [4,2,3,6] 3 [[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]], [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]] λ> particiones [4,2,3,6] 1 [[[4,2,3,6]]] λ> particiones [4,2,3,6] 4 [[[4],[2],[3],[6]]]
Soluciones
particiones :: [a] -> Int -> [[[a]]] particiones [] _ = [] particiones _ 0 = [] particiones xs 1 = [[xs]] particiones (x:xs) k = [[x]:ys | ys <- particiones xs (k-1)] ++ concat [inserta x ys | ys <- particiones xs k] -- (inserta x yss) es la lista obtenida insertando x en cada uno de los -- conjuntos de yss. Por ejemplo, -- inserta 4 [[3],[2,5]] == [[[4,3],[2,5]],[[3],[4,2,5]]] inserta :: a -> [[a]] -> [[[a]]] inserta x [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys:zss | zss <- inserta x yss] -- λ> particiones [2,3] 1 -- [[[2,3]]] -- λ> particiones [2,3] 2 -- [[[2],[3]]] -- λ> particiones [1,2,3] 1 -- [[[1,2,3]]] -- λ> particiones [1,2,3] 2 -- [[[1],[2,3]],[[1,2],[3]],[[2],[1,3]]] -- λ> particiones [1,2,3] 3 -- [[[1],[2],[3]]]