{"id":2861,"date":"2017-01-27T06:00:39","date_gmt":"2017-01-27T04:00:39","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2861"},"modified":"2017-02-03T09:02:37","modified_gmt":"2017-02-03T07:02:37","slug":"suma-minimal-de-productos-de-pares-de-elementos-consecutivos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/suma-minimal-de-productos-de-pares-de-elementos-consecutivos\/","title":{"rendered":"Suma minimal de productos de pares de elementos consecutivos"},"content":{"rendered":"<p>Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:<\/p>\n<ul>\n<li>10, por ejemplo con [1,4,2,3] ya que 1&#215;4+2&#215;3 = 10<\/li>\n<li>11, por ejemplo con [1,3,2,4] ya que 1&#215;3+2&#215;4 = 11<\/li>\n<li>14, por ejemplo con [1,2,3,4] ya que 1&#215;2+3&#215;4 = 14<\/li>\n<\/ul>\n<p>Por tanto, la m\u00ednima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutaci\u00f3n con dicha suma es [1,4,2,3].<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   minimaSumaProductos  :: (Num a, Ord a) => [a] -> a\n   permutacionMinimal   :: (Num a, Ord a) => [a] -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(minimaSumaProductos xs) es la m\u00ednima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un n\u00famero par de elementos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     minimaSumaProductos [1..4]             ==  10\n     minimaSumaProductos [3,2,5,7,1,6]      ==  34\n     minimaSumaProductos [9,2,8,4,5,7,6,0]  ==  74\n     minimaSumaProductos [1,2,1,4,0,5,6,0]  ==  6\n<\/pre>\n<ul>\n<li>(permutacionMinimal xs) es una permutaci\u00f3n de xs cuya suma de productos de elementos consecutivos de xs es la m\u00ednima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un n\u00famero par de elementos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     permutacionMinimal [1..4]             ==  [1,4,3,2]\n     permutacionMinimal [3,2,5,7,1,6]      ==  [1,7,2,6,3,5]\n     permutacionMinimal [9,2,8,4,5,7,6,0]  ==  [0,9,2,8,4,7,5,6]\n     permutacionMinimal [1,2,1,4,0,5,6,0]  ==  [0,6,0,5,1,4,1,2]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, permutations)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nminimaSumaProductos :: (Num a, Ord a) => [a] -> a\nminimaSumaProductos xs =\n  minimum [sumaProductos ys | ys <- permutations xs]\n\n--    sumaProductos [3,2,1,4]  ==  10\n--    sumaProductos [2,4,3,1]  ==  11\n--    sumaProductos [1,2,3,4]  ==  14\nsumaProductos :: (Num a, Ord a) => [a] -> a\nsumaProductos []       = 0\nsumaProductos [x]      = x\nsumaProductos (x:y:zs) = x*y + sumaProductos zs\n\npermutacionMinimal :: (Num a, Ord a) => [a] -> [a]\npermutacionMinimal xs =\n  head [ys | ys <- yss\n           , sumaProductos ys == m]\n  where yss = permutations xs\n        m   = minimaSumaProductos xs\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\npermutacionMinimal2 :: (Num a, Ord a) => [a] -> [a]\npermutacionMinimal2 xs =\n  intercala ys (reverse zs)\n  where n = length xs\n        (ys,zs) = splitAt (n `div` 2) (sort xs)\n\nintercala :: [a] -> [a] -> [a]\nintercala xs ys =\n  concat [[x,y] | (x,y) <- zip xs ys]\n\nminimaSumaProductos2 :: (Num a, Ord a) => [a] -> a\nminimaSumaProductos2 =\n  sumaProductos . permutacionMinimal2\n\n-- Equivalencia\n-- ============\n\nprop_equivalencia :: [Int] -> Property\nprop_equivalencia xs =\n  even (length xs) ==>\n  minimaSumaProductos xs == minimaSumaProductos2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos: 10, por ejemplo con [1,4,2,3] ya que 1&#215;4+2&#215;3 = 10 11, por ejemplo con [1,3,2,4] ya que 1&#215;3+2&#215;4 = 11 14, por ejemplo con [1,2,3,4] ya que 1&#215;2+3&#215;4 = 14 Por tanto, la m\u00ednima&#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":[4],"tags":[8,12,71,28,363,228,6,32,14,73],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2861"}],"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=2861"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2861\/revisions"}],"predecessor-version":[{"id":2895,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2861\/revisions\/2895"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}