{"id":4768,"date":"2019-02-27T06:00:47","date_gmt":"2019-02-27T04:00:47","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4768"},"modified":"2019-03-06T06:53:27","modified_gmt":"2019-03-06T04:53:27","slug":"numero-de-particiones-de-un-conjunto","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-particiones-de-un-conjunto\/","title":{"rendered":"N\u00famero de particiones de un conjunto"},"content":{"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:<\/p>\n

 \n   {{1}, {2}, {3}}\n   {{1,2}, {3}}\n   {{1,3}, {2}}\n   {{1}, {2,3}}\n   {{1,2,3}}\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
 \n   nParticiones :: [a] -> Integer\n<\/pre>\n
tal que (nParticiones xs) es el n\u00famero de particiones de xs. Por ejemplo,<\/p>\n
 \n   nParticiones [1,2]                     ==  2\n   nParticiones [1,2,3]                   ==  5\n   nParticiones \"abcd\"                    ==  15\n   length (show (nParticiones [1..500]))  ==  844\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List  ( genericLength\n                  )\nimport Data.Array ( Array\n                  , (!)\n                  , array\n                  )\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nnParticiones :: [a] -> Integer\nnParticiones xs =\n  genericLength (particiones xs)\n\n-- (particiones xs) es el conjunto de las particiones de xs. Por\n-- ejemplo, \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]]]\nparticiones :: [a] -> [[[a]]]\nparticiones [] = [[]]\nparticiones 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-- (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 definici\u00f3n\n-- =============\n\nnParticiones2 :: [a] -> Integer\nnParticiones2 xs = sum [nParticionesFijas n k | k <- [0..n]]\n  where n = genericLength xs\n\n-- nPparticionesFijas n k) es el n\u00famero de las particiones de un\n-- conjunto con n elementos en k subconjuntos. Por ejemplo,\n--    nParticionesFijas 3 0  ==  0\n--    nParticionesFijas 3 1  ==  1\n--    nParticionesFijas 3 2  ==  3\n--    nParticionesFijas 3 3  ==  1\n--    nParticionesFijas 3 4  ==  0\nnParticionesFijas :: Integer -> Integer -> Integer\nnParticionesFijas 0 0 = 1\nnParticionesFijas 0 _ = 0\nnParticionesFijas n 1 = 1\nnParticionesFijas n k = nParticionesFijas (n-1) (k-1) + k * nParticionesFijas (n-1) k\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\nnParticiones3 :: [a] -> Integer\nnParticiones3 xs = sum [a ! (n,k) | k <- [0..n]]\n  where n = genericLength xs\n        a = matrizNParticiones n\n\n-- (matrizNParticiones n) es la matriz de dimensi\u00f3n ((0,0),(n,n)) que en\n-- la posici\u00f3n (i,j) tiene el n\u00famero de particiones de un conjunto de i\n-- elementos en j subconjuntos. Por ejemplo,\n--    \u03bb> matrizNParticiones 3\n--    array ((0,0),(3,3))\n--          [((0,0),0),((0,1),0),((0,2),0),((0,3),0),\n--           ((1,0),0),((1,1),1),((1,2),0),((1,3),0),\n--           ((2,0),0),((2,1),1),((2,2),1),((2,3),0),\n--           ((3,0),0),((3,1),1),((3,2),3),((3,3),1)]\n--    \u03bb> matrizNParticiones 4\n--    array ((0,0),(4,4))\n--          [((0,0),0),((0,1),0),((0,2),0),((0,3),0),((0,4),0),\n--           ((1,0),0),((1,1),1),((1,2),0),((1,3),0),((1,4),0),\n--           ((2,0),0),((2,1),1),((2,2),1),((2,3),0),((2,4),0),\n--           ((3,0),0),((3,1),1),((3,2),3),((3,3),1),((3,4),0),\n--           ((4,0),0),((4,1),1),((4,2),7),((4,3),6),((4,4),1)]\nmatrizNParticiones :: Integer -> Array (Integer,Integer) Integer\nmatrizNParticiones n = a \n  where\n    a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]]\n    f 0 0 = 1\n    f 0 _ = 0\n    f _ 0 = 0\n    f _ 1 = 1\n    f i j = a ! (i-1,j-1) + j * a ! (i-1,j)\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\nnParticiones4 :: [a] -> Integer\nnParticiones4 xs = sum [a ! (n,k) | k <- [0..n]]\n  where\n    n = genericLength xs\n    a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]]\n    f 0 0 = 1\n    f 0 _ = 0\n    f _ 0 = 0\n    f _ 1 = 1\n    f i j = a ! (i-1,j-1) + j * a ! (i-1,j)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nParticiones [1..11]\n--    678570\n--    (3.77 secs, 705,537,480 bytes)\n--    \u03bb> nParticiones2 [1..11]\n--    678570\n--    (0.07 secs, 6,656,584 bytes)\n--    \u03bb> nParticiones3 [1..11]\n--    678570\n--    (0.01 secs, 262,176 bytes)\n--    \u03bb> nParticiones4 [1..11]\n--    678570\n--    (0.01 secs, 262,264 bytes)\n--    \n--    \u03bb> nParticiones2 [1..16]\n--    10480142147\n--    (2.24 secs, 289,774,408 bytes)\n--    \u03bb> nParticiones3 [1..16]\n--    10480142147\n--    (0.01 secs, 437,688 bytes)\n--    \u03bb> nParticiones4 [1..16]\n--    10480142147\n--    (0.01 secs, 437,688 bytes)\n--    \n--    \u03bb> length (show (nParticiones3 [1..500]))\n--    844\n--    (2.23 secs, 357,169,528 bytes)\n--    \u03bb> length (show (nParticiones4 [1..500]))\n--    844\n--    (2.20 secs, 357,172,680 bytes)\n<\/pre>\n
Pensamiento<\/h4>\n
\nYo he visto garras fieras en las pulidas manos;
\nconozco grajos m\u00e9licos y l\u00edricos marranos …
\nEl m\u00e1s truh\u00e1n se lleva la mano al coraz\u00f3n,
\ny el bruto m\u00e1s espeso se carga de raz\u00f3n.<\/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 nParticiones :: [a] -> Integer 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":[4],"tags":[250,8,12,286,258,28,6,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4768"}],"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=4768"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4768\/revisions"}],"predecessor-version":[{"id":4798,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4768\/revisions\/4798"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4768"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4768"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4768"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}