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:
permutacionesDivisibles :: Integer -> [[Integer]]
nPermutacionesDivisibles :: Integer -> Integer
tales que
- (permutacionesDivisibles n) es la lista de las permutaciones divisibles de {1,2,...,n}. Por ejemplo,
λ> 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,
nPermutacionesDivisibles 4 == 12
nPermutacionesDivisibles (10^8) `mod` (10^9) == 340332032
------------------------------------------------------------------------
<!-- TEASER_END -->
## Soluciones
~~~haskell
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)
