Se dice que A es un subconjunto maximal de B si A \u2282 B y no existe ning\u00fan C tal que A \u2282 C y C \u2282 B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es.<\/p>\n
El \u00e1rbol de los subconjuntos de un conjunto A es el \u00e1rbol que tiene como ra\u00edz el conjunto A y cada nodo tiene como hijos sus subconjuntos maximales. Por ejemplo, el \u00e1rbol de subconjuntos de [2,3,5] es<\/p>\n
\n [2, 3, 5]\n \/ | \\\n \/ | \\ \n \/ | \\ \n \/ | \\\n \/ | \\\n [5,3] [2,3] [2,5] \n \/ \\ \/ \\ \/ \\ \n [3] [5] [3] [2] [5] [2]\n | | | | | | \n [ ] [ ] [ ] [ ] [ ] [ ]\n<\/pre>\nUsando el tipo de dato<\/p>\n
\n data Arbol = N [Integer] [Arbol]\n deriving (Eq, Show)\n<\/pre>\nel \u00e1rbol anterior se representa por<\/p>\n
\n N [2,5,3]\n [N [5,3]\n [N [3]\n [N [] []],\n N [5]\n [N [] []]],\n N [2,3]\n [N [3]\n [N [] []],\n N [2]\n [N [] []]],\n N [2,5]\n [N [5]\n [N [] []],\n N [2]\n [N [] []]]]\n<\/pre>\nDefinir las funciones<\/p>\n
\n arbolSubconjuntos :: [Int] -> Arbol \n nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int\n<\/pre>\ntales que<\/p>\n
\n \u03bb> arbolSubconjuntos [2,5,3]\n N [2,5,3] [N [5,3] [N [3] [N [] []],N [5] [N [] []]],\n N [2,3] [N [3] [N [] []],N [2] [N [] []]],\n N [2,5] [N [5] [N [] []],N [2] [N [] []]]]\n<\/pre>\n\n nOcurrenciasArbolSubconjuntos [] [2,5,3] == 6\n nOcurrenciasArbolSubconjuntos [3] [2,5,3] == 2\n nOcurrenciasArbolSubconjuntos [3,5] [2,5,3] == 1\n nOcurrenciasArbolSubconjuntos [3,5,2] [2,5,3] == 1\n<\/pre>\nComprobar con QuickChek que, para todo entero positivo n, el n\u00famero de ocurrencia de un subconjunto xs de [1..n] en el \u00e1rbol de los subconjuntos de [1..n] es el factorial de n-k (donde k es el n\u00famero de elementos de xs).<\/p>\n
Soluciones<\/h4>\n\nimport Data.List (delete, nub, sort, subsequences)\nimport Test.QuickCheck\n\ndata Arbol = N [Int] [Arbol]\n deriving (Eq, Show)\n\narbolSubconjuntos :: [Int] -> Arbol \narbolSubconjuntos xs =\n N xs (map arbolSubconjuntos (subconjuntosMaximales xs))\n\n-- (subconjuntosMaximales xs) es la lista de los subconjuntos maximales\n-- de xs. Por ejemplo,\n-- subconjuntosMaximales [2,5,3] == [[5,3],[2,3],[2,5]]\nsubconjuntosMaximales :: [Int] -> [[Int]]\nsubconjuntosMaximales xs =\n [delete x xs | x <- xs]\n\n-- Definici\u00f3n de nOcurrenciasArbolSubconjuntos\n-- ===========================================\n\nnOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int\nnOcurrenciasArbolSubconjuntos xs ys =\n nOcurrencias xs (arbolSubconjuntos ys)\n\n-- (nOcurrencias x a) es el n\u00famero de veces que aparece x en el \u00e1rbol\n-- a. Por ejemplo,\n-- nOcurrencias 3 (arbolSubconjuntos 30) == 2\nnOcurrencias :: [Int] -> Arbol -> Int\nnOcurrencias xs (N ys [])\n | conjunto xs == conjunto ys = 1\n | otherwise = 0\nnOcurrencias xs (N ys zs)\n | conjunto xs == conjunto ys = 1 + sum [nOcurrencias xs z | z <- zs]\n | otherwise = sum [nOcurrencias xs z | z <- zs]\n\n-- (conjunto xs) es el conjunto ordenado correspondiente a xs. Por\n-- ejemplo, \n-- conjunto [3,2,5,2,3,7,2] == [2,3,5,7]\nconjunto :: [Int] -> [Int]\nconjunto = nub . sort\n\n-- La propiedad es\nprop_nOcurrencias :: (Positive Int) -> [Int] -> Bool\nprop_nOcurrencias (Positive n) xs =\n nOcurrenciasArbolSubconjuntos ys [1..n] == factorial (n-k)\n where ys = nub [1 + x `mod` n | x <- xs]\n k = length ys\n factorial m = product [1..m]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=9}) prop_nOcurrencias\n-- +++ OK, passed 100 tests.\n<\/pre>\nPensamiento<\/h4>\n\nNunca traces tu frontera,
\nni cuides de tu perfil;
\ntodo eso es cosa de fuera.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Se dice que A es un subconjunto maximal de B si A \u2282 B y no existe ning\u00fan C tal que A \u2282 C y C \u2282 B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es. El \u00e1rbol de los subconjuntos de un conjunto A es el \u00e1rbol 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":[269,8,25,28,10,89,24,11,157,6,14,40,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4471"}],"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=4471"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4471\/revisions"}],"predecessor-version":[{"id":4511,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4471\/revisions\/4511"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4471"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4471"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4471"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}