Definir la funci\u00f3n<\/p>\n
\n particiones :: [a] -> Int -> [[[a]]]\n<\/pre>\ntal que (particiones xs k)<\/code> es la lista de las particiones de xs<\/code> en k<\/code> subconjuntos disjuntos. Por ejemplo,<\/p>\n\n \u03bb> particiones [2,3,6] 2\n [[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]]\n \u03bb> particiones [2,3,6] 3\n [[[2],[3],[6]]]\n \u03bb> particiones [4,2,3,6] 3\n [[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]],\n [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]]\n \u03bb> particiones [4,2,3,6] 1\n [[[4,2,3,6]]]\n \u03bb> particiones [4,2,3,6] 4\n [[[4],[2],[3],[6]]]\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (nub, sort)\nimport Data.Array (Array, (!), array, listArray)\nimport Test.QuickCheck (Positive (Positive), quickCheckWith)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nparticiones1 :: [a] -> Int -> [[[a]]]\nparticiones1 [] _ = []\nparticiones1 _ 0 = []\nparticiones1 xs 1 = [[xs]]\nparticiones1 (x:xs) k = [[x]:ys | ys <- particiones1 xs (k-1)] ++ \n concat [inserta x ys | ys <- particiones1 xs k]\n\n-- (inserta x yss) es la lista obtenida insertando x en cada uno de los\n-- conjuntos de yss. Por ejemplo,\n-- inserta 4 [[3],[2,5]] == [[[4,3],[2,5]],[[3],[4,2,5]]]\ninserta :: a -> [[a]] -> [[[a]]]\ninserta _ [] = []\ninserta x (ys:yss) = ((x:ys):yss) : [ys:zss | zss <- inserta x yss]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nparticiones2 :: [a] -> Int -> [[[a]]]\nparticiones2 [] _ = []\nparticiones2 _ 0 = []\nparticiones2 xs 1 = [[xs]]\nparticiones2 (x:xs) k = map ([x]:) (particiones2 xs (k-1)) ++ \n concatMap (inserta x) (particiones2 xs k)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nparticiones3 :: [a] -> Int -> [[[a]]]\nparticiones3 xs k = matrizParticiones xs k ! (length xs, k)\n\nmatrizParticiones :: [a] -> Int -> Array (Int,Int) [[[a]]]\nmatrizParticiones xs k = q where\n q = array ((0,0),(n,k)) [((i,j), f i j) | i <- [0..n], j <- [0..k]]\n n = length xs\n v = listArray (1,n) xs\n f _ 0 = []\n f 0 _ = []\n f m 1 = [[take m xs]]\n f i j | i == j = [[[x] | x <- take i xs]]\n | otherwise = map ([v!i] :) (q!(i-1,j-1)) ++\n concatMap (inserta (v!i)) (q!(i-1,j))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_particiones :: [Int] -> Positive Int -> Bool\nprop_particiones xs (Positive k) =\n all (iguales (particiones1 xs' k))\n [particiones2 xs' k,\n particiones3 xs' k]\n where\n xs' = nub xs\n iguales xss yss = sort (map sort [map sort x | x <- xss]) ==\n sort (map sort [map sort y | y <- yss])\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_particiones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (particiones1 [1..12] 6)\n-- 1323652\n-- (1.33 secs, 1,152,945,584 bytes)\n-- \u03bb> length (particiones2 [1..12] 6)\n-- 1323652\n-- (1.07 secs, 1,104,960,360 bytes)\n-- \u03bb> length (particiones3 [1..12] 6)\n-- 1323652\n-- (1.68 secs, 1,047,004,368 bytes)\n<\/pre>\n