Permutaciones divisibles (OME2016 P5)
El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2016 es
De entre todas las permutaciones (a(1), a(2),…, a(n)) del conjunto {1, 2,…, n},(n ≥ 1 entero), se consideran las que cumplen que 2(a(1) + a(2) +···+ a(m)) es divisible por m, para cada m = 1, 2,…, n. Calcular el número total de estas permutaciones.
Llamaremos permutaciones divisibles a las que cumplen la propiedad anterior. Por ejemplo, [2,3,4,1] es una permutación divisible de {1,2,3,4} ya que es una permutación del conjunto y se cumplen las condiciones:
- 2*2 = 4 es divisible por 1,
- 2*(2+3) = 10 es divisible por 2
- 2*(2+3+4) = 18 es divisible por 3.
- 2*(2+3+4+1) = 20 es divisible por 4.
Definir las siguientes funciones:
1 2 |
permutacionesDivisibles :: Integer -> [[Integer]] nPermutacionesDivisibles :: Integer -> Integer |
tales que
- (permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,…,n}. Por ejemplo,
1 2 3 4 5 6 7 8 9 |
λ> permutacionesDivisibles 2 [[1,2],[2,1]] λ> permutacionesDivisibles 3 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] λ> permutacionesDivisibles 4 [[1,2,3,4],[1,3,2,4],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,3,1], [3,1,2,4],[3,2,1,4],[3,2,4,1],[3,4,2,1],[4,2,3,1],[4,3,2,1]] λ> length (permutacionesDivisibles 20) 786432 |
- (nPermutacionesDivisibles n) es el número de permutaciones divisibles de {1,2,…,n}. Por ejemplo,
1 2 |
nPermutacionesDivisibles 4 == 12 nPermutacionesDivisibles (10^8) `mod` (10^9) == 340332032 |
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 |
import Data.List (genericLength, permutations, sort) -- 1ª definición de permutacionesDivisibles -- ======================================== permutacionesDivisibles :: Integer -> [[Integer]] permutacionesDivisibles n = sort (filter aux (permutations [1..n])) where aux xs = and [(2*x) `mod` n == 0 | (x,n) <- zip (sumasParciales xs) [1..]] -- (sumasParciales xs) es la lista de las suas parciales de xs. Por ejemplo, -- sumasParciales [1..9] == [1,3,6,10,15,21,28,36,45] sumasParciales :: [Integer] -> [Integer] sumasParciales = scanl1 (+) -- 2ª definición de permutacionesDivisibles -- ======================================== permutacionesDivisibles2 :: Integer -> [[Integer]] permutacionesDivisibles2 = sort . aux where aux n | n < 4 = permutations [1..n] | otherwise = [xs ++ [n] | xs <- xss] ++ [map (+1) xs ++ [1] | xs <- xss] where xss = aux (n-1) -- Comprobación de equivalencia -- ============================ -- La comprobación para los n primeros valores es -- λ> and [permutacionesDivisibles2 n == permutacionesDivisibles n | n <- [1..9]] -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (permutacionesDivisibles 10) -- 768 -- (8.42 secs, 10,420,281,776 bytes) -- λ> length (permutacionesDivisibles2 10) -- 768 -- (0.02 secs, 2,250,152 bytes) -- -- λ> length (permutacionesDivisibles2 20) -- 786432 -- (14.33 secs, 4,458,839,736 bytes) -- 1ª definición de nPermutacionesDivisibles -- ========================================= -- nPermutacionesDivisibles 5 == 24 nPermutacionesDivisibles :: Integer -> Integer nPermutacionesDivisibles = genericLength . permutacionesDivisibles -- 2ª definición de nPermutacionesDivisibles -- ========================================= nPermutacionesDivisibles2 :: Integer -> Integer nPermutacionesDivisibles2 = genericLength . permutacionesDivisibles2 -- 3ª definición de nPermutacionesDivisibles -- ========================================= -- Observando los siguientes cálculos: -- λ> [nPermutacionesDivisibles2 n | n <- [1..12]] -- [1,2,6,12,24,48,96,192,384,768,1536,3072] -- λ> 1 : 2 : [3*2^(n-2) | n <- [3..12]] -- [1,2,6,12,24,48,96,192,384,768,1536,3072] nPermutacionesDivisibles3 :: Integer -> Integer nPermutacionesDivisibles3 n | n < 3 = n | otherwise = 3*2^(n-2) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> nPermutacionesDivisibles 10 -- 768 -- (7.95 secs, 10,704,422,592 bytes) -- λ> nPermutacionesDivisibles2 10 -- 768 -- (0.01 secs, 2,269,872 bytes) -- λ> nPermutacionesDivisibles3 10 -- 768 -- (0.01 secs, 102,560 bytes) -- -- λ> nPermutacionesDivisibles2 20 -- 786432 -- (13.00 secs, 4,477,717,968 bytes) -- λ> nPermutacionesDivisibles3 20 -- 786432 -- (0.01 secs, 106,848 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Sabiendo que para n>3 son las de n-1 transformadas pueden generarse directamente (sin poda)