Avanzado

Problema de las particiones óptimas

PorJosé A. Alonso 30-noviembre-20167-diciembre-2016

El problema de la particiones óptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partición óptima de xs. Por ejemplo, la partición óptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) – 5| = 0. Una lista puede tener distintas particiones óptimas. Por ejemplo, [1,1,2,3] tiene dos particiones óptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|).

Definir la función

   particionesOptimas :: [Int] -> [([Int],[Int])]

1	particionesOptimas :: [Int] -> [([Int],[Int])]

tal que (particionesOptimas xs) es la lista de las particiones óptimas de xs. Por ejemplo,

   particionesOptimas [2,3,5]    ==  [([2,3],[5])]
   particionesOptimas [1,1,2,3]  ==  [([1,2],[1,3]),([1,1,2],[3])]

1 2	particionesOptimas [2,3,5] == [([2,3],[5])] particionesOptimas [1,1,2,3] == [([1,2],[1,3]),([1,1,2],[3])]

Soluciones

import Data.List ((\\), nub, sort, subsequences)

-- Una partición es un par de lista de enteros.
type Particion = ([Int],[Int])

-- (particiones xs) es la lista de las particiones de xs. Por ejemplo,
--    λ> particiones [2,3,5]
--    [([],[2,3,5]),([2],[3,5]),([2,3],[5]),([2,5],[3])]
particiones :: [Int] -> [Particion]
particiones xs =
  [(sort ys, sort zs) | ys <- subsequences xs
                      , let zs = xs \\ ys
                      , ys <= zs]

-- (diferencia p) es el valor absoluto de la diferencia de las sumas de
-- los elementos de la partición p. Por ejemplo,
--    diferencia ([2],[3,5])  ==  6
--    diferencia ([2,3],[5])  ==  0
diferencia :: Particion -> Int
diferencia (xs,ys) = abs (sum xs - sum ys)

-- (diferenciasParticiones xs) es la lista de las diferencias de las
-- particiones de xs. Por ejemplo,
--    diferenciasParticiones [2,3,5]  ==  [10,6,0,4]
diferenciasParticiones :: [Int] -> [Int]
diferenciasParticiones xs = map diferencia (particiones xs)

-- (minDiferenciaParticiones xs) es el mínimo de las diferencias de las
-- particiones de xs. Por ejemplo, 
--    minDiferenciaParticiones [2,3,5]    ==  0
--    minDiferenciaParticiones [1,1,2,3]  ==  1
minDiferenciaParticiones :: [Int] -> Int
minDiferenciaParticiones = minimum . diferenciasParticiones

particionesOptimas :: [Int] -> [Particion]
particionesOptimas xs =
  nub [(ys,zs) | (ys,zs) <- particiones xs
               , diferencia (ys,zs) == m]
  where m = minDiferenciaParticiones xs

import Data.List ((\\), nub, sort, subsequences)

-- Una partición es un par de lista de enteros.

type Particion = ([Int],[Int])

-- (particiones xs) es la lista de las particiones de xs. Por ejemplo,

-- λ> particiones [2,3,5]

-- [([],[2,3,5]),([2],[3,5]),([2,3],[5]),([2,5],[3])]

particiones :: [Int] -> [Particion]

particiones xs =

[(sort ys, sort zs) | ys <- subsequences xs

, let zs = xs \\ ys

, ys <= zs]

-- (diferencia p) es el valor absoluto de la diferencia de las sumas de

-- los elementos de la partición p. Por ejemplo,

-- diferencia ([2],[3,5]) == 6

-- diferencia ([2,3],[5]) == 0

diferencia :: Particion -> Int

diferencia (xs,ys) = abs (sum xs - sum ys)

-- (diferenciasParticiones xs) es la lista de las diferencias de las

-- particiones de xs. Por ejemplo,

-- diferenciasParticiones [2,3,5] == [10,6,0,4]

diferenciasParticiones :: [Int] -> [Int]

diferenciasParticiones xs = map diferencia (particiones xs)

-- (minDiferenciaParticiones xs) es el mínimo de las diferencias de las

-- particiones de xs. Por ejemplo,

-- minDiferenciaParticiones [2,3,5] == 0

-- minDiferenciaParticiones [1,1,2,3] == 1

minDiferenciaParticiones :: [Int] -> Int

minDiferenciaParticiones = minimum . diferenciasParticiones

particionesOptimas :: [Int] -> [Particion]

particionesOptimas xs =

nub [(ys,zs) | (ys,zs) <- particiones xs

, diferencia (ys,zs) == m]

where m = minDiferenciaParticiones xs

Mínimo número de operaciones para transformar un número en otro

PorJosé A. Alonso 25-noviembre-201625-marzo-2022

Se considera el siguiente par de operaciones sobre los números:

multiplicar por dos
restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

   4 ------> 8 ------> 7
      (x2)      (-1)

1 2	4 ------> 8 ------> 7 (x2) (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

   2 ------> 4 ------> 3 ------> 6 ------> 5
      (x2)      (-1)      (x2)      (-1)

1 2	2 ------> 4 ------> 3 ------> 6 ------> 5 (x2) (-1) (x2) (-1)

Definir las siguientes funciones

   arbolOp :: Int -> Int -> Arbol
   minNOp  :: Int -> Int -> Int

1 2	arbolOp :: Int -> Int -> Arbol minNOp :: Int -> Int -> Int

tales que

(arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

    λ> arbolOp 4 1
    N 4 (H 8) (H 3)
    λ> arbolOp 4 2
    N 4 (N 8 (H 16) (H 7))
        (N 3 (H 6) (H 2))
    λ> arbolOp 2 3
    N 2 (N 4
           (N 8 (H 16) (H 7))
           (N 3 (H 6) (H 2)))
        (N 1
           (N 2 (H 4) (H 1))
           (H 0))
    λ> arbolOp 2 4
    N 2 (N 4 (N 8
                (N 16 (H 32) (H 15))
                (N 7 (H 14) (H 6)))
             (N 3
                (N 6 (H 12) (H 5))
                (N 2 (H 4) (H 1))))
        (N 1 (N 2
                (N 4 (H 8) (H 3))
                (N 1 (H 2) (H 0)))
             (H 0))

λ> arbolOp 4 1

N 4 (H 8) (H 3)

λ> arbolOp 4 2

N 4 (N 8 (H 16) (H 7))

(N 3 (H 6) (H 2))

λ> arbolOp 2 3

N 2 (N 4

(N 8 (H 16) (H 7))

(N 3 (H 6) (H 2)))

(N 1

(N 2 (H 4) (H 1))

(H 0))

λ> arbolOp 2 4

N 2 (N 4 (N 8

(N 16 (H 32) (H 15))

(N 7 (H 14) (H 6)))

(N 3

(N 6 (H 12) (H 5))

(N 2 (H 4) (H 1))))

(N 1 (N 2

(N 4 (H 8) (H 3))

(N 1 (H 2) (H 0)))

(H 0))

(minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

     minNOp 4 7  ==  2
     minNOp 2 5  ==  4

1 2	minNOp 4 7 == 2 minNOp 2 5 == 4

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol
           deriving Show

arbolOp :: Int -> Int -> Arbol
arbolOp 0 _ = H 0
arbolOp x 0 = H x
arbolOp x n = N x (arbolOp (2 * x) (n - 1)) (arbolOp (x - 1) (n - 1))

ocurre :: Int -> Arbol -> Bool
ocurre x (H y)     = x == y
ocurre x (N y i d) = x == y || ocurre x i || ocurre x d

minNOp :: Int -> Int -> Int
minNOp x y =
  head [n | n <- [0..]
          , ocurre y (arbolOp x n)]

data Arbol = H Int

| N Int Arbol Arbol

deriving Show

arbolOp :: Int -> Int -> Arbol

arbolOp 0 _ = H 0

arbolOp x 0 = H x

arbolOp x n = N x (arbolOp (2 * x) (n - 1)) (arbolOp (x - 1) (n - 1))

ocurre :: Int -> Arbol -> Bool

ocurre x (H y) = x == y

ocurre x (N y i d) = x == y || ocurre x i || ocurre x d

minNOp :: Int -> Int -> Int

minNOp x y =

head [n | n <- [0..]

, ocurre y (arbolOp x n)]

Referencias

Basado en el artículo Minimum number of operation required to
convert number x into y de Vipin Khushu en
GeeksforGeeks.

Menor potencia de 2 comenzando un número dado

PorJosé A. Alonso 24-noviembre-20161-diciembre-2016

Definir las siguientes funciones

   potenciasDe2  :: Integer -> [Integer]
   menorPotenciaDe2 :: Integer -> Integer

1 2	potenciasDe2 :: Integer -> [Integer] menorPotenciaDe2 :: Integer -> Integer

tales que

(potenciasDe2 a) es la lista de las potencias de 2 que comienzan por a. Por ejemplo,

     λ> take 5 (potenciasDe2 3)
     [32,32768,33554432,34359738368,35184372088832]
     λ> take 2 (potenciasDe2 102)
     [1024,102844034832575377634685573909834406561420991602098741459288064]

λ> take 5 (potenciasDe2 3)

[32,32768,33554432,34359738368,35184372088832]

λ> take 2 (potenciasDe2 102)

[1024,102844034832575377634685573909834406561420991602098741459288064]

(menorPotenciaDe2 a) es la menor potencia de 2 que comienza con el número a. Por ejemplo,

     λ> menorPotenciaDe2 10
     1024
     λ> menorPotenciaDe2 25
     256
     λ> menorPotenciaDe2 62
     6277101735386680763835789423207666416102355444464034512896
     λ> menorPotenciaDe2 425
     42535295865117307932921825928971026432
     λ> menorPotenciaDe2 967140655691
     9671406556917033397649408
     λ> [menorPotenciaDe2 a | a <- [1..10]]
     [1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

λ> menorPotenciaDe2 10

1024

λ> menorPotenciaDe2 25

256

λ> menorPotenciaDe2 62

6277101735386680763835789423207666416102355444464034512896

λ> menorPotenciaDe2 425

42535295865117307932921825928971026432

λ> menorPotenciaDe2 967140655691

9671406556917033397649408

λ> [menorPotenciaDe2 a | a <- [1..10]]

[1,2,32,4,512,64,70368744177664,8,9007199254740992,1024]

Comprobar con QuickCheck que, para todo entero positivo a, existe una potencia de 2 que empieza por a.

Soluciones

import Data.List (isPrefixOf)
import Test.QuickCheck

-- 1ª definición de potenciasDe2
-- =============================

potenciasDe2A :: Integer -> [Integer]
potenciasDe2A a =
  [x | x <- potenciasA
     , a `esPrefijo` x]

potenciasA :: [Integer]
potenciasA = [2^n | n <- [0..]]

esPrefijo :: Integer -> Integer -> Bool
esPrefijo x y = show x `isPrefixOf` show y

-- 2ª definición de potenciasDe2
-- =============================

potenciasDe2B :: Integer -> [Integer]
potenciasDe2B a = filter (a `esPrefijo`) potenciasA

-- 3ª definición de potenciasDe2
-- =============================

potenciasDe2C :: Integer -> [Integer]
potenciasDe2C a = filter (a `esPrefijo`) potenciasC

potenciasC :: [Integer]
potenciasC = iterate (*2) 1

-- Comparación de eficiencia
-- =========================

-- λ> length (show (head (potenciasDe2A 123456)))
-- 19054
-- (7.17 secs, 1,591,992,792 bytes)
-- λ> length (show (head (potenciasDe2B 123456)))
-- 19054
-- (5.96 secs, 1,273,295,272 bytes)
-- λ> length (show (head (potenciasDe2C 123456)))
-- 19054
-- (6.24 secs, 1,542,698,392 bytes)

-- Definición de menorPotenciaDe2 
menorPotenciaDe2 :: Integer -> Integer
menorPotenciaDe2 = head . potenciasDe2B

-- Propiedad
prop_potenciasDe2 :: Integer -> Property
prop_potenciasDe2 a =
  a > 0 ==> not (null (potenciasDe2B a))

-- Comprobación
--    λ> quickCheck prop_potenciasDe2
--    +++ OK, passed 100 tests.

import Data.List (isPrefixOf)

import Test.QuickCheck

-- 1ª definición de potenciasDe2

-- =============================

potenciasDe2A :: Integer -> [Integer]

potenciasDe2A a =

[x | x <- potenciasA

, a `esPrefijo` x]

potenciasA :: [Integer]

potenciasA = [2^n | n <- [0..]]

esPrefijo :: Integer -> Integer -> Bool

esPrefijo x y = show x `isPrefixOf` show y

-- 2ª definición de potenciasDe2

-- =============================

potenciasDe2B :: Integer -> [Integer]

potenciasDe2B a = filter (a `esPrefijo`) potenciasA

-- 3ª definición de potenciasDe2

-- =============================

potenciasDe2C :: Integer -> [Integer]

potenciasDe2C a = filter (a `esPrefijo`) potenciasC

potenciasC :: [Integer]

potenciasC = iterate (*2) 1

-- Comparación de eficiencia

-- =========================

-- λ> length (show (head (potenciasDe2A 123456)))

-- 19054

-- (7.17 secs, 1,591,992,792 bytes)

-- λ> length (show (head (potenciasDe2B 123456)))

-- 19054

-- (5.96 secs, 1,273,295,272 bytes)

-- λ> length (show (head (potenciasDe2C 123456)))

-- 19054

-- (6.24 secs, 1,542,698,392 bytes)

-- Definición de menorPotenciaDe2

menorPotenciaDe2 :: Integer -> Integer

menorPotenciaDe2 = head . potenciasDe2B

-- Propiedad

prop_potenciasDe2 :: Integer -> Property

prop_potenciasDe2 a =

a > 0 ==> not (null (potenciasDe2B a))

-- Comprobación

-- λ> quickCheck prop_potenciasDe2

-- +++ OK, passed 100 tests.

Referencias

Potencias de 2 por Philippe Chevanne en «Mad Maths».
Sucesión A018802 de la OEIS

Máxima ramificación

PorJosé A. Alonso 23-noviembre-201630-noviembre-2016

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
                  deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

     1         1             1          
    / \       / \           / \   
   2   3     2   3         2   3  
       |        /|\       /|\  |   
       4       4 5 6     4 5 6 7

1 1 1

/ \ / \ / \

2 3 2 3 2 3

| /|\ /|\ |

4 4 5 6 4 5 6 7

se representan por

   ej1, ej2, ej3 :: Arbol Int
   ej1 = N 1 [N 2 [],N 3 [N 4 []]]
   ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]
   ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

ej1, ej2, ej3 :: Arbol Int

ej1 = N 1 [N 2 [],N 3 [N 4 []]]

ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]

ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

En el primer ejemplo la máxima ramificación es 2 (en el nodo 1 que tiene 2 hijos), la del segundo es 3 (en el nodo 3 que tiene 3 hijos) y la del tercero es 3 (en el nodo 3 que tiene 3 hijos).

Definir la función

   maximaRamificacion :: Arbol a -> Int

1	maximaRamificacion :: Arbol a -> Int

tal que (maximaRamificacion a) es la máxima ramificación del árbol a. Por ejemplo,

   maximaRamificacion ej1  ==  2
   maximaRamificacion ej2  ==  3
   maximaRamificacion ej3  ==  3

maximaRamificacion ej1 == 2

maximaRamificacion ej2 == 3

maximaRamificacion ej3 == 3

Soluciones

data Arbol a = N a [Arbol a]
  deriving Show

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]]
ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]] 

maximaRamificacion :: Arbol a -> Int
maximaRamificacion (N _ []) = 0
maximaRamificacion (N x xs) =
  max (length xs) (maximum (map maximaRamificacion xs))

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [],N 3 [N 4 []]]

ej2 = N 1 [N 2 [], N 3 [N 4 [], N 5 [], N 6 []]]

ej3 = N 1 [N 2 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

maximaRamificacion :: Arbol a -> Int

maximaRamificacion (N _ []) = 0

maximaRamificacion (N x xs) =

max (length xs) (maximum (map maximaRamificacion xs))

Números consecutivos compuestos

PorJosé A. Alonso 22-noviembre-201629-noviembre-2016

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

   menorSerieCompuesta :: Integer -> (Integer,Integer)

1	menorSerieCompuesta :: Integer -> (Integer,Integer)

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

   menorSerieCompuesta 3    ==  (8,10)
   menorSerieCompuesta 4    ==  (24,27)
   menorSerieCompuesta 5    ==  (24,28)
   menorSerieCompuesta 150  ==  (4652354,4652503)

menorSerieCompuesta 3 == (8,10)

menorSerieCompuesta 4 == (24,27)

menorSerieCompuesta 5 == (24,28)

menorSerieCompuesta 150 == (4652354,4652503)

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

-- 1ª definición
-- =============

menorSerieCompuesta1 :: Integer -> (Integer,Integer)
menorSerieCompuesta1 n = (x,x+n-1)
  where x = head [y | y <- [1..]
                    , esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool
esCompuesta xs =  all (not . isPrime) xs

-- 2ª definición
-- =============

menorSerieCompuesta2 :: Integer -> (Integer,Integer)
menorSerieCompuesta2 n = (x+1,x+n)
  where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)
                            , q - p >= n + 1]

-- Comparación de eficiencia
-- =========================

--    λ> menorSerieCompuesta1 75
--    (155922,155996)
--    (12.16 secs, 30,378,380,552 bytes)
--    λ> menorSerieCompuesta2 75
--    (155922,155996)
--    (0.07 secs, 89,813,752 bytes)


-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_menorSerieCompuesta :: Integer -> Property
prop_menorSerieCompuesta n =
  n > 1 ==> x == y || y == z
  where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

-- La comprobación es
--    λ> quickCheck prop_menorSerieCompuesta
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª definición

-- =============

menorSerieCompuesta1 :: Integer -> (Integer,Integer)

menorSerieCompuesta1 n = (x,x+n-1)

where x = head [y | y <- [1..]

, esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool

esCompuesta xs = all (not . isPrime) xs

-- 2ª definición

-- =============

menorSerieCompuesta2 :: Integer -> (Integer,Integer)

menorSerieCompuesta2 n = (x+1,x+n)

where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)

, q - p >= n + 1]

-- Comparación de eficiencia

-- =========================

-- λ> menorSerieCompuesta1 75

-- (155922,155996)

-- (12.16 secs, 30,378,380,552 bytes)

-- λ> menorSerieCompuesta2 75

-- (155922,155996)

-- (0.07 secs, 89,813,752 bytes)

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_menorSerieCompuesta :: Integer -> Property

prop_menorSerieCompuesta n =

n > 1 ==> x == y || y == z

where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

-- La comprobación es

-- λ> quickCheck prop_menorSerieCompuesta

-- +++ OK, passed 100 tests.

Referencias

Sucesión A030296 de la OEIS.

Problema de las particiones óptimas

Soluciones

Mínimo número de operaciones para transformar un número en otro

Soluciones

Referencias

Menor potencia de 2 comenzando un número dado

Soluciones

Referencias

Máxima ramificación

Soluciones

Números consecutivos compuestos

Soluciones

Referencias

Entradas recientes

Buscar

Correo electrónico