Número de particiones de un conjunto
Una partición de un conjunto A es un conjunto de subconjuntos no vacíos de A, disjuntos dos a dos y cuya unión es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:
|
1 2 3 4 5 |
{{1}, {2}, {3}} {{1,2}, {3}} {{1,3}, {2}} {{1}, {2,3}} {{1,2,3}} |
Definir la función
|
1 |
nParticiones :: [a] -> Integer |
tal que (nParticiones xs) es el número de particiones de xs. Por ejemplo,
|
1 2 3 4 |
nParticiones [1,2] == 2 nParticiones [1,2,3] == 5 nParticiones "abcd" == 15 length (show (nParticiones [1..500])) == 844 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
import Data.List ( genericLength ) import Data.Array ( Array , (!) , array ) -- 1ª definición -- ============= nParticiones :: [a] -> Integer nParticiones xs = genericLength (particiones xs) -- (particiones xs) es el conjunto de las particiones de xs. Por -- ejemplo, -- λ> particiones [1,2] -- [[[1,2]],[[1],[2]]] -- λ> particiones [1,2,3] -- [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]] particiones :: [a] -> [[[a]]] particiones [] = [[]] particiones xs = concat [particionesFijas xs k | k <- [0..length xs]] -- (particionesFijas xs k) es el conjunto de las particiones de xs en k -- subconjuntos. Por ejemplo, -- particionesFijas [1,2,3] 0 == [] -- particionesFijas [1,2,3] 1 == [[[1,2,3]]] -- particionesFijas [1,2,3] 2 == [[[1],[2,3]],[[1,2],[3]],[[2],[1,3]]] -- particionesFijas [1,2,3] 3 == [[[1],[2],[3]]] -- particionesFijas [1,2,3] 4 == [] particionesFijas :: [a] -> Int -> [[[a]]] particionesFijas [] _ = [] particionesFijas xs 1 = [[xs]] particionesFijas (x:xs) k = [[x]:ys | ys <- particionesFijas xs (k-1)] ++ concat [inserta x ys | ys <- particionesFijas xs k] -- (inserta x yss) es la lista obtenida insertando x en cada uno de los -- elementos de yss. Por ejemplo, -- λ> inserta 1 [[2,3],[4],[5,6,7]] -- [[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]] inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] -- 2ª definición -- ============= nParticiones2 :: [a] -> Integer nParticiones2 xs = sum [nParticionesFijas n k | k <- [0..n]] where n = genericLength xs -- nPparticionesFijas n k) es el número de las particiones de un -- conjunto con n elementos en k subconjuntos. Por ejemplo, -- nParticionesFijas 3 0 == 0 -- nParticionesFijas 3 1 == 1 -- nParticionesFijas 3 2 == 3 -- nParticionesFijas 3 3 == 1 -- nParticionesFijas 3 4 == 0 nParticionesFijas :: Integer -> Integer -> Integer nParticionesFijas 0 0 = 1 nParticionesFijas 0 _ = 0 nParticionesFijas n 1 = 1 nParticionesFijas n k = nParticionesFijas (n-1) (k-1) + k * nParticionesFijas (n-1) k -- 3ª definición -- ============= nParticiones3 :: [a] -> Integer nParticiones3 xs = sum [a ! (n,k) | k <- [0..n]] where n = genericLength xs a = matrizNParticiones n -- (matrizNParticiones n) es la matriz de dimensión ((0,0),(n,n)) que en -- la posición (i,j) tiene el número de particiones de un conjunto de i -- elementos en j subconjuntos. Por ejemplo, -- λ> matrizNParticiones 3 -- array ((0,0),(3,3)) -- [((0,0),0),((0,1),0),((0,2),0),((0,3),0), -- ((1,0),0),((1,1),1),((1,2),0),((1,3),0), -- ((2,0),0),((2,1),1),((2,2),1),((2,3),0), -- ((3,0),0),((3,1),1),((3,2),3),((3,3),1)] -- λ> matrizNParticiones 4 -- array ((0,0),(4,4)) -- [((0,0),0),((0,1),0),((0,2),0),((0,3),0),((0,4),0), -- ((1,0),0),((1,1),1),((1,2),0),((1,3),0),((1,4),0), -- ((2,0),0),((2,1),1),((2,2),1),((2,3),0),((2,4),0), -- ((3,0),0),((3,1),1),((3,2),3),((3,3),1),((3,4),0), -- ((4,0),0),((4,1),1),((4,2),7),((4,3),6),((4,4),1)] matrizNParticiones :: Integer -> Array (Integer,Integer) Integer matrizNParticiones n = a where a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]] f 0 0 = 1 f 0 _ = 0 f _ 0 = 0 f _ 1 = 1 f i j = a ! (i-1,j-1) + j * a ! (i-1,j) -- 4ª definición -- ============= nParticiones4 :: [a] -> Integer nParticiones4 xs = sum [a ! (n,k) | k <- [0..n]] where n = genericLength xs a = array ((0,0),(n,n)) [((i,j), f i j) | i <- [0..n], j <- [0..n]] f 0 0 = 1 f 0 _ = 0 f _ 0 = 0 f _ 1 = 1 f i j = a ! (i-1,j-1) + j * a ! (i-1,j) -- Comparación de eficiencia -- ========================= -- λ> nParticiones [1..11] -- 678570 -- (3.77 secs, 705,537,480 bytes) -- λ> nParticiones2 [1..11] -- 678570 -- (0.07 secs, 6,656,584 bytes) -- λ> nParticiones3 [1..11] -- 678570 -- (0.01 secs, 262,176 bytes) -- λ> nParticiones4 [1..11] -- 678570 -- (0.01 secs, 262,264 bytes) -- -- λ> nParticiones2 [1..16] -- 10480142147 -- (2.24 secs, 289,774,408 bytes) -- λ> nParticiones3 [1..16] -- 10480142147 -- (0.01 secs, 437,688 bytes) -- λ> nParticiones4 [1..16] -- 10480142147 -- (0.01 secs, 437,688 bytes) -- -- λ> length (show (nParticiones3 [1..500])) -- 844 -- (2.23 secs, 357,169,528 bytes) -- λ> length (show (nParticiones4 [1..500])) -- 844 -- (2.20 secs, 357,172,680 bytes) |
Pensamiento
Yo he visto garras fieras en las pulidas manos;
conozco grajos mélicos y líricos marranos …
El más truhán se lleva la mano al corazón,
y el bruto más espeso se carga de razón.Antonio Machado