Una partici\u00f3n de un conjunto A es un conjunto de subconjuntos no vac\u00edos de A, disjuntos dos a dos y cuya uni\u00f3n es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:<\/p>\n
\n {{1}, {2}, {3}}\n {{1,2}, {3}}\n {{1,3}, {2}}\n {{1}, {2,3}}\n {{1,2,3}}\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n particiones :: [a] -> [[[a]]]\n<\/pre>\ntal que (particiones xs) es el conjunto de las particiones de xs. Por ejemplo,<\/p>\n
\n \u03bb> particiones [1,2]\n [[[1,2]],[[1],[2]]]\n \u03bb> particiones [1,2,3]\n [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]\n \u03bb> particiones \"abcd\"\n [[\"abcd\"],[\"a\",\"bcd\"],[\"ab\",\"cd\"],[\"b\",\"acd\"],[\"abc\",\"d\"],[\"bc\",\"ad\"],\n [\"ac\",\"bd\"],[\"c\",\"abd\"],[\"a\",\"b\",\"cd\"],[\"a\",\"bc\",\"d\"],[\"a\",\"c\",\"bd\"],\n [\"ab\",\"c\",\"d\"],[\"b\",\"ac\",\"d\"],[\"b\",\"c\",\"ad\"],[\"a\",\"b\",\"c\",\"d\"]]\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nparticiones :: [a] -> [[[a]]]\nparticiones [] = [[]]\nparticiones (x:xs) =\n concat [([x] : yss) : inserta x yss | yss <- ysss]\n where ysss = particiones xs\n\n-- (inserta x yss) es la lista obtenida insertando x en cada uno de los\n-- elementos de yss. Por ejemplo, \n-- \u03bb> inserta 1 [[2,3],[4],[5,6,7]]\n-- [[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]]\ninserta :: a -> [[a]] -> [[[a]]]\ninserta _ [] = []\ninserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nparticiones2 :: [a] -> [[[a]]]\nparticiones2 [] = [[]]\nparticiones2 xs =\n concat [particionesFijas xs k | k <- [0..length xs]]\n\n-- (particionesFijas xs k) es el conjunto de las particiones de xs en k\n-- subconjuntos. Por ejemplo,\n-- particionesFijas [1,2,3] 0 == []\n-- particionesFijas [1,2,3] 1 == [[[1,2,3]]]\n-- particionesFijas [1,2,3] 2 == [[[1],[2,3]],[[1,2],[3]],[[2],[1,3]]]\n-- particionesFijas [1,2,3] 3 == [[[1],[2],[3]]]\n-- particionesFijas [1,2,3] 4 == []\nparticionesFijas :: [a] -> Int -> [[[a]]]\nparticionesFijas [] _ = []\nparticionesFijas xs 1 = [[xs]]\nparticionesFijas (x:xs) k =\n [[x]:ys | ys <- particionesFijas xs (k-1)] ++\n concat [inserta x ys | ys <- particionesFijas xs k]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nparticiones3 :: [a] -> [[[a]]]\nparticiones3 xs = concat [a ! (n,k) | k <- [0..n]]\n where a = matrizParticiones xs\n n = length xs\n\n-- (matrizParticiones xs) es la matriz de dimensi\u00f3n ((0,0),(n,n)) que en\n-- la posici\u00f3n (i,j) tiene el conjunto de particiones de los i primeros\n-- elementoa de xs en j subconjuntos. Por ejemplo,\n-- \u03bb> elems (matrizParticiones [1,2,3])\n-- [[[]],[], [], [],\n-- [], [[[1]]], [], [],\n-- [], [[[1,2]]], [[[2],[1]]], [],\n-- [], [[[1,2,3]]],[[[3],[1,2]],[[3,2],[1]],[[2],[3,1]]],[[[3],[2],[1]]]]\nmatrizParticiones :: [a] -> Array (Int,Int) [[[a]]]\nmatrizParticiones xs = a \n where\n n = length xs\n v = listArray (1,n) xs\n a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]]\n f 0 0 = [[]]\n f 0 _ = []\n f _ 0 = []\n f i 1 = [[[v!k | k <- [1..i]]]]\n f i j = [[v!i] : ys | ys <- a!(i-1,j-1)] ++\n concat [inserta (v!i) ys | ys <- a!(i-1,j)]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_Particiones :: [Int] -> Bool\nprop_Particiones xs =\n all (== (ordenada . particiones) xs)\n [(ordenada . f )xs | f <- [ particiones2\n , particiones3]]\n \nordenada :: Ord a => [[[a]]] -> [[[a]]]\nordenada xsss =\n sort [sort (map sort xss) | xss <- xsss]\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-- \u03bb> length (particiones [1..12])\n-- 4213597\n-- (2.74 secs, 2,903,492,120 bytes)\n-- \u03bb> length (particiones2 [1..12])\n-- 4213597\n-- (4.63 secs, 3,878,003,920 bytes)\n-- \u03bb> length (particiones3 [1..12])\n-- 4213597\n-- (6.21 secs, 3,199,076,464 bytes)\n<\/pre>\nPensamiento<\/h4>\n\nA quien nos justifica nuestra desconfianza
\nllamamos enemigo, ladr\u00f3n de una esperanza.
\nJam\u00e1s perdona el necio si ve la nuez vac\u00eda
\nque dio a cascar al diente de la sabidur\u00eda.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Una partici\u00f3n de un conjunto A es un conjunto de subconjuntos no vac\u00edos de A, disjuntos dos a dos y cuya uni\u00f3n es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones: {{1}, {2}, {3}} {{1,2}, {3}} {{1,3}, {2}} {{1}, {2,3}} {{1,2,3}} Definir la funci\u00f3n particiones :: [a] -> [[[a]]] tal que…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[8,12,28,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4766"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4766"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4766\/revisions"}],"predecessor-version":[{"id":4792,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4766\/revisions\/4792"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4766"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}