sort

Ofertas 3 por 2

PorJosé A. Alonso 3-enero-201825-abril-2021

En una tienda tienen la «oferta 3 por 2» de forma que cada cliente que elige 3 artículos obtiene el más barato de forma gratuita. Por ejemplo, si los precios de los artículos elegidos por un cliente son 10, 2, 4, 5 euros pagará 19 euros si agrupa los artículos en (10,2,4) y (5) o pagará 17 si lo agupa en (5,10,4) y (2).

Definir la función

   minimoConOferta :: [Int] -> Int

1	minimoConOferta :: [Int] -> Int

tal que (minimoConOferta xs) es lo mínimo que pagará el cliente si los precios de la compra son xs; es decir, lo que pagará agrupando los artículos de forma óptima para aplicar la oferta 3 por 2. Por ejemplo,

   minimoConOferta [10,2,4,5]     ==  17
   minimoConOferta [3,2,3,2]      ==  8
   minimoConOferta [6,4,5,5,5,5]  ==  21

minimoConOferta [10,2,4,5] == 17

minimoConOferta [3,2,3,2] == 8

minimoConOferta [6,4,5,5,5,5] == 21

Soluciones

import Data.List (sort)

minimoConOferta :: [Int] -> Int
minimoConOferta xs = aux (reverse (sort xs)) 0
  where aux (a:b:_:ds) n = aux ds (a+b+n)
        aux as         n = n + sum as

import Data.List (sort)

minimoConOferta :: [Int] -> Int

minimoConOferta xs = aux (reverse (sort xs)) 0

where aux (a:b:_:ds) n = aux ds (a+b+n)

aux as n = n + sum as

El problema 3SUM

PorJosé A. Alonso 2-enero-201819-febrero-2018

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

   sols3Sum :: [Int] -> [[Int]]
   pb3Sum :: [Int] -> Bool

1 2	sols3Sum :: [Int] -> [[Int]] pb3Sum :: [Int] -> Bool

tales que
+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,

      sols3Sum [8,10,-10,-7,2,-3]   ==  [[-10,2,8],[-7,-3,10]]
      sols3Sum [-2..3]              ==  [[-2,-1,3],[-2,0,2],[-1,0,1]]
      sols3Sum [1,-2]               ==  []
      sols3Sum [-2,1]               ==  []
      sols3Sum [1,-2,1]             ==  [[-2,1,1]]
      length (sols3Sum [-100..100]) ==  5000

sols3Sum [8,10,-10,-7,2,-3] == [[-10,2,8],[-7,-3,10]]

sols3Sum [-2..3] == [[-2,-1,3],[-2,0,2],[-1,0,1]]

sols3Sum [1,-2] == []

sols3Sum [-2,1] == []

sols3Sum [1,-2,1] == [[-2,1,1]]

length (sols3Sum [-100..100]) == 5000

(pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,

     pb3Sum [8,10,-10,-7,2,-3]  ==  True
     pb3Sum [1,-2]              ==  False
     pb3Sum [-2,1]              ==  False
     pb3Sum [1,-2,1]            ==  True
     pb3Sum [1..400]            ==  False

pb3Sum [8,10,-10,-7,2,-3] == True

pb3Sum [1,-2] == False

pb3Sum [-2,1] == False

pb3Sum [1,-2,1] == True

pb3Sum [1..400] == False

Soluciones

import Data.List

-- 1ª solución
-- ===========

sols3Sum1 :: [Int] -> [[Int]]
sols3Sum1 = normaliza . sols3Sum1Aux 

sols3Sum1Aux :: [Int] -> [[Int]]
sols3Sum1Aux xs =
  [ys | ys <- subsequences xs
      , length ys == 3
      , sum ys == 0]

normaliza :: [[Int]] -> [[Int]]
normaliza = sort . nub . map sort

pb3Sum1 :: [Int] -> Bool
pb3Sum1 = not . null . sols3Sum1Aux


-- 2ª solución
-- ===========

sols3Sum2 :: [Int] -> [[Int]]
sols3Sum2 = normaliza . sols3Sum2Aux 

sols3Sum2Aux :: [Int] -> [[Int]]
sols3Sum2Aux xs =
  [[a,b,c] | (a:bs) <- tails xs
           , (b:cs) <- tails bs
           , c <- cs
           , a + b + c == 0]
  
pb3Sum2 :: [Int] -> Bool
pb3Sum2 = not . null . sols3Sum2Aux

-- 3ª solución
-- ===========

sols3Sum3 :: [Int] -> [[Int]]
sols3Sum3 = normaliza . sols3Sum3Aux 

sols3Sum3Aux :: [Int] -> [[Int]]
sols3Sum3Aux xs =
  [[a,b,-a-b] | (a:bs) <- tails xs
              , b <- bs
              , (-a-b) `elem` (delete a (delete b xs))]

pb3Sum3 :: [Int] -> Bool
pb3Sum3 = not . null . sols3Sum3Aux

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

--    λ> pb3Suma [1..23]
--    False
--    (2.61 secs, 1,812,734,176 bytes)
--    λ> pb3Sumb [1..23]
--    False
--    (0.01 secs, 554,496 bytes)
--    λ> pb3Sumc [1..23]
--    False
--    (0.01 secs, 584,344 bytes)
--    λ> pb3Suma ([1..23] ++ [-3]) 
--    True
--    (2.54 secs, 1,812,735,784 bytes)
--    λ> pb3Sumb ([1..23] ++ [-3]) 
--    True
--    (0.01 secs, 148,904 bytes)
--    λ> pb3Sumc ([1..23] ++ [-3]) 
--    True
--    (0.00 secs, 145,320 bytes)
--
--    λ> pb3Sumb [1..300]
--    False
--    (1.66 secs, 933,699,824 bytes)
--    λ> pb3Sumc [1..300]
--    False
--    (0.41 secs, 873,168,120 bytes)

import Data.List

-- 1ª solución

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

sols3Sum1 :: [Int] -> [[Int]]

sols3Sum1 = normaliza . sols3Sum1Aux

sols3Sum1Aux :: [Int] -> [[Int]]

sols3Sum1Aux xs =

[ys | ys <- subsequences xs

, length ys == 3

, sum ys == 0]

normaliza :: [[Int]] -> [[Int]]

normaliza = sort . nub . map sort

pb3Sum1 :: [Int] -> Bool

pb3Sum1 = not . null . sols3Sum1Aux

-- 2ª solución

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

sols3Sum2 :: [Int] -> [[Int]]

sols3Sum2 = normaliza . sols3Sum2Aux

sols3Sum2Aux :: [Int] -> [[Int]]

sols3Sum2Aux xs =

[[a,b,c] | (a:bs) <- tails xs

, (b:cs) <- tails bs

, c <- cs

, a + b + c == 0]

pb3Sum2 :: [Int] -> Bool

pb3Sum2 = not . null . sols3Sum2Aux

-- 3ª solución

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

sols3Sum3 :: [Int] -> [[Int]]

sols3Sum3 = normaliza . sols3Sum3Aux

sols3Sum3Aux :: [Int] -> [[Int]]

sols3Sum3Aux xs =

[[a,b,-a-b] | (a:bs) <- tails xs

, b <- bs

, (-a-b) `elem` (delete a (delete b xs))]

pb3Sum3 :: [Int] -> Bool

pb3Sum3 = not . null . sols3Sum3Aux

-- Comparación de eficiencia

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

-- λ> pb3Suma [1..23]

-- False

-- (2.61 secs, 1,812,734,176 bytes)

-- λ> pb3Sumb [1..23]

-- False

-- (0.01 secs, 554,496 bytes)

-- λ> pb3Sumc [1..23]

-- False

-- (0.01 secs, 584,344 bytes)

-- λ> pb3Suma ([1..23] ++ [-3])

-- True

-- (2.54 secs, 1,812,735,784 bytes)

-- λ> pb3Sumb ([1..23] ++ [-3])

-- True

-- (0.01 secs, 148,904 bytes)

-- λ> pb3Sumc ([1..23] ++ [-3])

-- True

-- (0.00 secs, 145,320 bytes)

-- λ> pb3Sumb [1..300]

-- False

-- (1.66 secs, 933,699,824 bytes)

-- λ> pb3Sumc [1..300]

-- False

-- (0.41 secs, 873,168,120 bytes)

Ordenación según una cadena

PorJosé A. Alonso 29-diciembre-201726-marzo-2022

Dada una lista xs y una cadena cs de la misma longitud, la ordenación de xs según cs consiste en emparejar los elementos de cs con los de xs (de forma que al menor elemento de cs le corresponde el menor de xs, al segundo de cs el segundo de xs, etc.) y ordenar los elementos de xs en el mismo orden que sus correspondientes elementos de cs. Por ejemplo, si xs es [6,4,2] y cs es «CAB» entonces a ‘A’ le corresponde el 2, a ‘B’ el 4 y a ‘C’ el 6; luego la ordenación es [6,2,4].

Definir la función

   ordenacion :: Ord a => [a] -> String -> [a]

1	ordenacion :: Ord a => [a] -> String -> [a]

tal que (ordenacion xs ys) es la ordenación de la lista xs según la cadena cs. Por ejemplo,

   ordenacion [6,4,2] "CAB"     ==  [6,2,4]
   ordenacion [1,5,3] "ABC"     ==  [1,3,5]
   ordenacion [1,5,3,7] "ABEC"  ==  [1,3,7,5]

ordenacion [6,4,2] "CAB" == [6,2,4]

ordenacion [1,5,3] "ABC" == [1,3,5]

ordenacion [1,5,3,7] "ABEC" == [1,3,7,5]

Soluciones

import Data.List (sort)
import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]
ordenacion xs cs =
  [fromJust (lookup y diccionario) | y <- cs]
  where diccionario = zip (sort cs) (sort xs)

import Data.List (sort)

import Data.Maybe (fromJust)

ordenacion :: Ord a => [a] -> String -> [a]

ordenacion xs cs =

[fromJust (lookup y diccionario) | y <- cs]

where diccionario = zip (sort cs) (sort xs)

Ordenación valle

PorJosé A. Alonso 8-diciembre-201715-diciembre-2017

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
las dos partes tienen el mismo número de elementos;
cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

   valle :: [Int] -> [Int]

1	valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

   valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
   valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
   valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
   valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
   valle [14,14,14,14,14]             ==  [14,14,14,14,14]
   valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

valle [79,35,54,19,35,25,12] == [79,35,25,12,19,35,54]

valle [79,35,54,19,35,25] == [79,35,25,19,35,54]

valle [67,93,100,-16,65,97,92] == [100,93,67,-16,65,92,97]

valle [14,14,14,14,7,14] == [14,14,14,7,14,14]

valle [14,14,14,14,14] == [14,14,14,14,14]

valle [17,17,15,14,8,7,7,5,4,4,1] == [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 – 7 > 17 – 17.

Soluciones

import Data.List (sort, sortBy)

-- 1ª solución
valle1 :: [Int] -> [Int]
valle1 xs = ys ++ reverse zs
  where (ys,zs) = aux (reverse (sort xs))
        aux []       = ([],[])
        aux [x]      = ([x],[])
        aux [x,y]    = ([x,y],[])
        aux (x:y:zs) = (x:as,y:bs)
          where (as,bs) = aux zs

-- 2ª solución
valle2 :: [Int] -> [Int]
valle2 = aux . reverse . sort
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]

-- 3ª solución
valle3 :: [Int] -> [Int]
valle3 = aux . sortBy (flip compare)
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]
        
-- Comparación de eficiencia
-- =========================

-- λ> length (valle1 [1..2*10^4])
-- 20000
-- (0.02 secs, 8,621,240 bytes)
-- λ> length (valle2 [1..2*10^4])
-- 20000
-- (2.68 secs, 8,595,637,880 bytes)
-- λ> length (valle3 [1..2*10^4])
-- 20000
-- (2.67 secs, 8,594,678,104 bytes)

import Data.List (sort, sortBy)

-- 1ª solución

valle1 :: [Int] -> [Int]

valle1 xs = ys ++ reverse zs

where (ys,zs) = aux (reverse (sort xs))

aux [] = ([],[])

aux [x] = ([x],[])

aux [x,y] = ([x,y],[])

aux (x:y:zs) = (x:as,y:bs)

where (as,bs) = aux zs

-- 2ª solución

valle2 :: [Int] -> [Int]

valle2 = aux . reverse . sort

where aux [] = []

aux [x] = [x]

aux (x:y:xs) = x : aux xs ++ [y]

-- 3ª solución

valle3 :: [Int] -> [Int]

valle3 = aux . sortBy (flip compare)

where aux [] = []

aux [x] = [x]

aux (x:y:xs) = x : aux xs ++ [y]

-- Comparación de eficiencia

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

-- λ> length (valle1 [1..2*10^4])

-- 20000

-- (0.02 secs, 8,621,240 bytes)

-- λ> length (valle2 [1..2*10^4])

-- 20000

-- (2.68 secs, 8,595,637,880 bytes)

-- λ> length (valle3 [1..2*10^4])

-- 20000

-- (2.67 secs, 8,594,678,104 bytes)

Conjunto de funciones entre dos conjuntos

PorJosé A. Alonso 1-diciembre-20178-diciembre-2017

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

[(1,2),(3,6)] es una función de [1,3] en [2,4,6];
[(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
[(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

   funciones  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
   nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

1 2	funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]] nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

(funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo,

     λ> funciones [1] [2]
     [[(1,2)]]
     λ> funciones [1] [2,4]
     [[(1,2)],[(1,4)]]
     λ> funciones [1,3] [2]
     [[(1,2),(3,2)]]
     λ> funciones [1,3] [2,4]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]
     λ> funciones [1,3] [2,4,6]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],
      [(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],
      [(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]
     λ> funciones [1,3,5] [2,4]
     [[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],
      [(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],
      [(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]
     λ> funciones [] []
     [[]]
     λ> funciones [] [2]
     [[]]
     λ> funciones [1] []
     []

λ> funciones [1] [2]

[[(1,2)]]

λ> funciones [1] [2,4]

[[(1,2)],[(1,4)]]

λ> funciones [1,3] [2]

[[(1,2),(3,2)]]

λ> funciones [1,3] [2,4]

[[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]

λ> funciones [1,3] [2,4,6]

[[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],

[(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],

[(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]

λ> funciones [1,3,5] [2,4]

[[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],

[(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],

[(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]

λ> funciones [] []

[[]]

λ> funciones [] [2]

[[]]

λ> funciones [1] []

[]

(nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo,

     nFunciones [1,3] [2,4,6]  ==  9
     nFunciones [1,3,5] [2,4]  ==  8
     length (show (nFunciones2 [1..10^6] [1..10^3]))  ==  3000001

nFunciones [1,3] [2,4,6] == 9

nFunciones [1,3,5] [2,4] == 8

length (show (nFunciones2 [1..10^6] [1..10^3])) == 3000001

Soluciones

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

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

funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones xs ys =
  conjunto [r | r <- relaciones xs ys
              , esFuncion r xs ys]

-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs
-- e ys. Por ejemplo,
--    λ> relaciones [1,3] [2,4]
--    [[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
--     [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
--     [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
--     [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
--     [(1,2),(1,4),(3,2),(3,4)]]
relaciones :: [a] -> [b] -> [[(a,b)]]
relaciones xs ys =
  subsequences (producto xs ys)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,
--    producto [1,3] [2,4]  ==  [(1,2),(1,4),(3,2),(3,4)]
producto :: [a] -> [b] -> [(a,b)]
producto xs ys =
  [(x,y) | x <- xs, y <- ys]

-- (esFuncional r) r se verifica si la relación r es funcional. Por
-- ejemplo, 
--    esFuncional [(2,4),(1,5),(3,4)]        ==  True
--    esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False
esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
esFuncional r =
  and [esUnitario (imagen r x) | x <- dominio r] 

-- (dominio r) es el dominio de la relación r. Por ejemplo,
--    dominio [(5,4),(1,4),(1,2),(3,4)]  ==  [1,3,5]
dominio :: Ord a => [(a,b)] -> [a]
dominio = sort . nub . map fst

-- (imagen r x) es la imagen de x en la relación r. Por ejemplo,
--    imagen [(5,4),(1,4),(1,2),(3,4)] 1  ==  [2,4]
--    imagen [(5,4),(1,4),(1,2),(3,4)] 2  ==  []
imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]
imagen r x =
  conjunto [y | (x1,y) <- r, x1 == x]

-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos
-- distintos) correspondiente a la lista xs. Por ejemplo, 
--    conjunto [7,2,3,2,7,3]  ==  [2,3,7]
conjunto :: Ord a => [a] -> [a]
conjunto = sort . nub

-- (esUnitario xs) se verifica si xs tiene sólo un elemento.
esUnitario :: [a] -> Bool
esUnitario xs =
  length xs == 1

-- (esFuncion r xs ys) se verifica si r es una función con dominio xs y
-- codominio ys. Por ejemplo,
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  True
--    esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7]     ==  False
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7]     ==  False
--    esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  False
esFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool
esFuncion r xs ys =
     conjunto xs == dominio r 
  && rango r `contenido` conjunto ys
  && esFuncional r

-- (rango r) es el rango de la relación r. Por ejemplo,
--    rango [(5,4),(1,4),(1,2),(3,4)]  ==  [2,4]
rango :: Ord b => [(a,b)] -> [b]
rango = sort . nub . map snd

-- (contenido xs ys) se verifica si el conjunto xs está contenido en el
-- ys. Por ejemplo,
--    [1,3] `contenido` [1,2,3,5]  ==  True
--    [1,3] `contenido` [1,2,4,5]  ==  False
contenido :: Ord a => [a] -> [a] -> Bool 
contenido xs ys =
  all (`elem` ys) xs

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

funciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones2 xs ys =
  conjunto (aux xs ys)
  where aux [] _      = [[]]
        aux [x] ys    = [[(x,y)] | y <- ys]
        aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
          where fs = aux xs ys

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

--    λ> length (funciones [1..4] [1..4]) 
--    256
--    (2.69 secs, 754,663,072 bytes)
--    λ> length (funciones2 [1..4] [1..4]) 
--    256
--    (0.04 secs, 243,600 bytes)

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

nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys =
  genericLength (funciones2 xs ys)

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

nFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones2 xs ys =
  (genericLength ys)^(genericLength xs)

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

--    λ> nFunciones [1..5] [1..5] 
--    3125
--    (1.35 secs, 1,602,872 bytes)
--    λ> nFunciones2 [1..5] [1..5] 
--    3125
--    (0.03 secs, 140,480 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

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

-- 1ª definición de funciones

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

funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]

funciones xs ys =

conjunto [r | r <- relaciones xs ys

, esFuncion r xs ys]

-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs

-- e ys. Por ejemplo,

-- λ> relaciones [1,3] [2,4]

-- [[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],

-- [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],

-- [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],

-- [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],

-- [(1,2),(1,4),(3,2),(3,4)]]

relaciones :: [a] -> [b] -> [[(a,b)]]

relaciones xs ys =

subsequences (producto xs ys)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,

-- producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

producto :: [a] -> [b] -> [(a,b)]

producto xs ys =

[(x,y) | x <- xs, y <- ys]

-- (esFuncional r) r se verifica si la relación r es funcional. Por

-- ejemplo,

-- esFuncional [(2,4),(1,5),(3,4)] == True

-- esFuncional [(3,4),(1,4),(1,2),(3,4)] == False

esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

esFuncional r =

and [esUnitario (imagen r x) | x <- dominio r]

-- (dominio r) es el dominio de la relación r. Por ejemplo,

-- dominio [(5,4),(1,4),(1,2),(3,4)] == [1,3,5]

dominio :: Ord a => [(a,b)] -> [a]

dominio = sort . nub . map fst

-- (imagen r x) es la imagen de x en la relación r. Por ejemplo,

-- imagen [(5,4),(1,4),(1,2),(3,4)] 1 == [2,4]

-- imagen [(5,4),(1,4),(1,2),(3,4)] 2 == []

imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]

imagen r x =

conjunto [y | (x1,y) <- r, x1 == x]

-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos

-- distintos) correspondiente a la lista xs. Por ejemplo,

-- conjunto [7,2,3,2,7,3] == [2,3,7]

conjunto :: Ord a => [a] -> [a]

conjunto = sort . nub

-- (esUnitario xs) se verifica si xs tiene sólo un elemento.

esUnitario :: [a] -> Bool

esUnitario xs =

length xs == 1

-- (esFuncion r xs ys) se verifica si r es una función con dominio xs y

-- codominio ys. Por ejemplo,

-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7] == True

-- esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7] == False

-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7] == False

-- esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7] == False

esFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool

esFuncion r xs ys =

conjunto xs == dominio r

&& rango r `contenido` conjunto ys

&& esFuncional r

-- (rango r) es el rango de la relación r. Por ejemplo,

-- rango [(5,4),(1,4),(1,2),(3,4)] == [2,4]

rango :: Ord b => [(a,b)] -> [b]

rango = sort . nub . map snd

-- (contenido xs ys) se verifica si el conjunto xs está contenido en el

-- ys. Por ejemplo,

-- [1,3] `contenido` [1,2,3,5] == True

-- [1,3] `contenido` [1,2,4,5] == False

contenido :: Ord a => [a] -> [a] -> Bool

contenido xs ys =

all (`elem` ys) xs

-- 2ª definición de funciones

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

funciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]

funciones2 xs ys =

conjunto (aux xs ys)

where aux [] _ = [[]]

aux [x] ys = [[(x,y)] | y <- ys]

aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]

where fs = aux xs ys

-- Comparación de eficiencia de funciones

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

-- λ> length (funciones [1..4] [1..4])

-- 256

-- (2.69 secs, 754,663,072 bytes)

-- λ> length (funciones2 [1..4] [1..4])

-- 256

-- (0.04 secs, 243,600 bytes)

-- 1ª definición de nFunciones

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

nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

nFunciones xs ys =

genericLength (funciones2 xs ys)

-- 2ª definición de nFunciones

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

nFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer

nFunciones2 xs ys =

(genericLength ys)^(genericLength xs)

-- Comparación de eficiencia de nFunciones

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

-- λ> nFunciones [1..5] [1..5]

-- 3125

-- (1.35 secs, 1,602,872 bytes)

-- λ> nFunciones2 [1..5] [1..5]

-- 3125

-- (0.03 secs, 140,480 bytes)

Ofertas 3 por 2

Soluciones

El problema 3SUM

Soluciones

Ordenación según una cadena

Soluciones

Ordenación valle

Soluciones

Conjunto de funciones entre dos conjuntos

Soluciones

Entradas recientes

Buscar

Correo electrónico