Definir la funci\u00f3n<\/p>\n
\n numeroParticiones :: Int -> Int -> Int\n<\/pre>\ntal que (numeroParticiones n k)<\/code> es el n\u00famero de particiones de conjunto de n<\/code> elementos en k<\/code> subconjuntos disjuntos. Por ejemplo,<\/p>\n\n numeroParticiones 3 2 == 3\n numeroParticiones 3 3 == 1\n numeroParticiones 4 3 == 6\n numeroParticiones 4 1 == 1\n numeroParticiones 4 4 == 1\n numeroParticiones 91 89 == 8139495\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array (Array, (!), array)\nimport Test.QuickCheck (Positive (Positive), quickCheckWith)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParticiones1 :: Int -> Int -> Int\nnumeroParticiones1 n k =\n length (particiones1 [1..n] k)\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\nnumeroParticiones2 :: Int -> Int -> Int\nnumeroParticiones2 0 _ = 0\nnumeroParticiones2 _ 0 = 0\nnumeroParticiones2 _ 1 = 1\nnumeroParticiones2 n k = k * numeroParticiones2 (n-1) k +\n numeroParticiones2 (n-1) (k-1) \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParticiones3 :: Int -> Int -> Int\nnumeroParticiones3 n k = matrizNumeroParticiones n k ! (n,k)\n\nmatrizNumeroParticiones :: Int -> Int -> Array (Int,Int) Int\nmatrizNumeroParticiones n k = q where\n q = array ((0,0),(n,k)) [((i,j), f i j) | i <- [0..n], j <- [0..k]]\n f _ 0 = 0\n f 0 _ = 0\n f _ 1 = 1\n f i j | i == j = 1\n | otherwise = j * f (i-1) j + f (i-1) (j-1)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_numeroParticiones :: Positive Int -> Positive Int -> Bool\nprop_numeroParticiones (Positive n) (Positive k) =\n all (== numeroParticiones1 n k)\n [numeroParticiones2 n k,\n numeroParticiones3 n k]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_numeroParticiones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> numeroParticiones1 12 6\n-- 1323652\n-- (1.22 secs, 1,152,945,608 bytes)\n-- \u03bb> numeroParticiones2 12 6\n-- 1323652\n-- (0.00 secs, 1,283,152 bytes)\n-- \u03bb> numeroParticiones3 12 6\n-- 1323652\n-- (0.01 secs, 1,155,864 bytes)\n--\n-- \u03bb> numeroParticiones2 21 19\n-- 19285\n-- (2.04 secs, 990,274,976 bytes)\n-- \u03bb> numeroParticiones3 21 19\n-- 19285\n-- (0.00 secs, 940,736 bytes)\n<\/pre>\n