{"id":4968,"date":"2019-04-30T06:00:12","date_gmt":"2019-04-30T04:00:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4968"},"modified":"2019-05-19T19:16:03","modified_gmt":"2019-05-19T17:16:03","slug":"numero-de-emparejamientos-de-amigos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-emparejamientos-de-amigos\/","title":{"rendered":"N\u00famero de emparejamientos de amigos"},"content":{"rendered":"<p>El <strong>problema del n\u00famero de emparejamiento de amigos<\/strong> consiste en calcular el n\u00famero de formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con alg\u00fan otro amigo y que cada amigo puede ser emparejado s\u00f3lo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos son<\/p>\n<pre lang=\"text\"> \n   {1}, {2}, {3} \n   {1}, {2, 3} \n   {1, 2}, {3} \n   {1, 3}, {2}\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\"> \n   nEmparejamientos :: Integer -> Integer\n<\/pre>\n<p>tal que (nEmparejamientos n) es el n\u00famero de formas de emparejar a los n amigos. Por ejemplo,<\/p>\n<pre lang=\"text\"> \n   nEmparejamientos 2   ==  2\n   nEmparejamientos 3   ==  4\n   nEmparejamientos 4   ==  10\n   nEmparejamientos 10  ==  9496\n   nEmparejamientos 30  ==  606917269909048576\n   length (show (nEmparejamientos3 (10^4)))  ==  17872\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (delete, genericLength)\nimport Data.Array\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnEmparejamientos :: Integer -> Integer\nnEmparejamientos = genericLength . emparejamientos\n\nemparejamientos :: Integer -> [[[Integer]]]\nemparejamientos n = aux [1..n]\n  where aux [] = [[]]\n        aux (x:xs) = [[x] : ps | ps <- aux xs] ++\n                     [[x,y] : ps | y <- xs, ps <- aux (delete y xs)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnEmparejamientos2 :: Integer -> Integer\nnEmparejamientos2 0 = 1\nnEmparejamientos2 1 = 1\nnEmparejamientos2 2 = 2\nnEmparejamientos2 n = nEmparejamientos2 (n - 1) + (n - 1) * nEmparejamientos2 (n - 2)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnEmparejamientos3 :: Integer -> Integer\nnEmparejamientos3 n = (vectorEmparejamientos n) ! n\n\n-- (vectorEmparejamientos n) es el vector con \u00edndices de 0 a n tal que el valor\n-- de la posici\u00f3n i es el n\u00famero de formas de emparejar a i amigos. Por ejemplo,\n--    \u03bb> vectorEmparejamientos 7\n--    array (0,7) [(0,1),(1,1),(2,2),(3,4),(4,10),(5,26),(6,76),(7,232)]\nvectorEmparejamientos :: Integer -> Array Integer Integer\nvectorEmparejamientos n = v where\n  v = array (0,n) [(i,f i) | i <- [0..n]]\n  f 0 = 1\n  f 1 = 1\n  f 2 = 2\n  f n = v!(n-1) + (n-1)*v!(n-2)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nEmparejamientos 12\n--    140152\n--    (1.81 secs, 280,218,616 bytes)\n--    \u03bb> nEmparejamientos2 12\n--    140152\n--    (0.01 secs, 177,168 bytes)\n--    \u03bb> nEmparejamientos3 12\n--    140152\n--    (0.01 secs, 108,816 bytes)\n--    \n--    \u03bb> nEmparejamientos2 30\n--    606917269909048576\n--    (3.97 secs, 449,224,280 bytes)\n--    \u03bb> nEmparejamientos3 30\n--    606917269909048576\n--    (0.01 secs, 135,160 bytes)\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nToda la imaginer\u00eda<br \/>\nque no ha brotado del r\u00edo,<br \/>\nbarata bisuter\u00eda.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El problema del n\u00famero de emparejamiento de amigos consiste en calcular el n\u00famero de formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con alg\u00fan otro amigo y que cada amigo puede ser emparejado s\u00f3lo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos&#8230;<\/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":[250,8,25,286,258,6],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4968"}],"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=4968"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4968\/revisions"}],"predecessor-version":[{"id":5028,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4968\/revisions\/5028"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}