Menu Close

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:

   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

Soluciones

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>
Ejercicio

5 soluciones de “Permutaciones divisibles (OME2016 P5)

  1. Joaquín Infante Rodríguez
     
    import Data.List
     
    listaDivisible :: [Integer] -> Bool
    listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]
     
    permutacionesDivisibles  :: Integer -> [[Integer]]
    permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]
     
    nPermutacionesDivisibles :: Integer -> Integer
    nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)
  2. j0sejuan
    {-
     
      Una propiedad de poda de recursión puede ser que:
     
             2 a1 = 1 · k1
      2 a1 + 2 a2 = 2 · k2
              ... = ...
     
               2 a{i-1} + ... = (i-1) · k{i-1}
      2 a{i} + 2 a{i-1} + ... =  i    · k{i  }
     
      Restando
     
      2 a{i} + (i-1) · k{i-1} = i · k{i}
     
      Es decir, para cada nuevo sumando se debe cumplir que:
     
      k1   = 2 a1
      k{i} = (2 a{i} + (i-1) · k{i-1}) / i
     
    -}
    permutacionesDivisibles :: Integer -> [[Integer]]
    permutacionesDivisibles n = rec [] [1..n] 1 0
      where rec rs [] _ _ = return rs
            rec rs xs i k = do
              a <- xs
              case (2 * a + (i - 1) * k) `divMod` i of
                (k', 0) -> rec (a:rs) (filter (a /= ) xs) (i + 1) k'
                _       -> []
     
    {-
     
    *Main> mapM_ (print . length . permutacionesDivisibles) [1..]
    1
    2
    6
    12
    24
    48
    96
    192
    384
    768
    1536
    3072
    6144
    12288
    24576
    49152
    98304
    196608
    393216
    786432
    1572864
    3145728
    ...
     
    -}
     
    -- No caigo de exactamente porqué, pero siguen la progresión:
    nPermutacionesDivisibles :: Integer -> Integer
    nPermutacionesDivisibles 1 = 1
    nPermutacionesDivisibles 2 = 2
    nPermutacionesDivisibles 3 = 6
    nPermutacionesDivisibles n = 2 * nPermutacionesDivisibles (n - 1)
     
    -- que para n>=3 puede escribirse como 6 * 2^(n - 3)
  3. j0sejuan
    -- Perdón, buscando la razón me perdí, no importa mucho pero más simple checar la suma directamente
    permutacionesDivisibles :: Integer -> [[Integer]]
    permutacionesDivisibles n = rec [] [1..n] 1 0
      where rec rs [] _ _ = return rs
            rec rs xs i s = do
              a <- xs
              let s' = 2 * a + s
              guard $ s' `mod` i == 0
              rec (a:rs) (filter (a /= ) xs) (i + 1) s'
  4. j0sejuan

    Sabiendo que para n>3 son las de n-1 transformadas pueden generarse directamente (sin poda)

    todasPermutacionesDivisibles :: [[[Integer]]]
    todasPermutacionesDivisibles = [[1]]:[[1,2],[2,1]]:rec 4 (permutations [1..3])
      where rec z xs = xs: rec (z+1) (map (++[z]) xs ++ map ((++[1]).(map (+1))) xs)
     
    permutacionesDivisibles :: Integer -> [[Integer]]
    permutacionesDivisibles n = todasPermutacionesDivisibles!!(fromInteger n - 1)
     
    {-
     
    *Main> length $ permutacionesDivisibles 27
    100663296
    (26.08 secs, 23,354,014,440 bytes)
     
    -}
  5. María Ruiz
    import Data.List
     
    listaDivisible :: [Integer] -> Bool
    listaDivisible xs = and [rem (2*(sum (genericTake n xs))) n == 0 | n<-[1..genericLength xs]]
     
    permutacionesDivisibles  :: Integer -> [[Integer]]
    permutacionesDivisibles n = [xs | xs<-permutations [1..n] , listaDivisible xs]
     
    nPermutacionesDivisibles :: Integer -> Integer
    nPermutacionesDivisibles n = genericLength (permutacionesDivisibles n)
     
    -- permutacionesDivisibles 3
    -- [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
    -- permutacionesDivisibles 4
    -- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],
    --  [4,3,2,1],[3,4,2,1],[3,2,4,1],[4,2,3,1],[2,4,3,1],[2,3,4,1]]
     
    -- Reordenando:
    -- [[1,2,3,4],[2,1,3,4],[3,2,1,4],[2,3,1,4],[3,1,2,4],[1,3,2,4],
    --  [2,3,4,1],[3,2,4,1],[4,3,2,1],[3,4,2,1],[4,2,3,1],[2,4,3,1]]
     
    -- Parece que sigue el patrón siguiente, a partir de n = 4:
    -- 
     
    permutacionesDivisibles2  :: Integer -> [[Integer]]
    permutacionesDivisibles2 1 = permutations [1]
    permutacionesDivisibles2 2 = permutations [1,2]
    permutacionesDivisibles2 3 = permutations [1,2,3]
    permutacionesDivisibles2 n = map (++[n]) xss ++ map f xss
      where xss = permutacionesDivisibles2 (n-1)
            f xs = (map (+1) xs) ++ [1]
     
    -- length (permutacionesDivisibles2 20) == 786432
     
    -- Usando evaluación perezosa
     
    sucPerDiv :: [[[Integer]]]
    sucPerDiv = (permutations [1]):(permutations [1,2]): iterate g (permutations [1,2,3])
      where g xss = map (++[n]) xss ++ map f xss
              where n = 1 + genericLength (head xss)
                    f xs = (map (+1) xs) ++ [1]
     
    permutacionesDivisibles3  :: Integer -> [[Integer]]
    permutacionesDivisibles3 n = sucPerDiv `genericIndex` (n-1)
     
    -- Comparación de eficiencia:
     
    -- length (permutacionesDivisibles2 20) == 786432
    -- (0.18 secs, 182,535,376 bytes)
    -- length (permutacionesDivisibles3 20) == 786432
    -- (0.27 secs, 182,538,936 bytes)
     
    -- Segunda definición del número de permutaciones:
     
    sucNumPerDiv :: [Integer]
    sucNumPerDiv = 1:2:iterate (*2) 6
     
    nPermutacionesDivisibles2 :: Integer -> Integer
    nPermutacionesDivisibles2 n = sucNumPerDiv `genericIndex` (n-1)
     
     
    -- Observación:
     
    -- take 20 sucNumPerDiv
    -- [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]
    -- λ> import Data.Numbers.Primes
    -- λ> map primeFactors [1,2,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,98304,196608,393216,786432]
    -- [[],[2],[2,3],[2,2,3],[2,2,2,3],[2,2,2,2,3],[2,2,2,2,2,3],[2,2,2,2,2,2,3],[2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,3],
    --  [2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,3],
    --  [2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],
    --  [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3],[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]]
     
    -- Tercera definición:
     
    nPermutacionesDivisibles3 :: Integer -> Integer
    nPermutacionesDivisibles3 1 = 1
    nPermutacionesDivisibles3 2 = 2
    nPermutacionesDivisibles3 n = 3*2^(n-2)
     
    -- nPermutacionesDivisibles3 (10^8) `mod` (10^9) == 340332032

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.