Cadenas de divisores

5 Comentarios

1. Haskell

   cadenasDivisores :: Int -> [[Int]] cadenasDivisores 1 = [[1]] cadenasDivisores n = map (++ [n]) (concatMap cadenasDivisores (divisores n)) where divisores n = [x | x <- [1..n-1], rem n x == 0]

   1 2 3 4

   cadenasDivisores :: Int -> [[Int]] cadenasDivisores 1 = [[1]] cadenasDivisores n = map (++ [n]) (concatMap cadenasDivisores (divisores n))     where divisores n = [x | x <- [1..n-1], rem n x == 0]

   Responder

2. Puede hacerse tan eficiente como la generación de todos los divisores si al generar los divisores se almacena la relación generadora a partir de la descomposición en factores. Aquí no se almacena dicha relación y se revisa divisibilidad. Aun así, tiene la misma complejidad («sólo» ahorraríamos la división en cada caso).

   Haskell

   import Data.List (init, tail, group) import Data.Numbers.Primes cadenasDivisores :: ℤ → [[ℤ]] cadenasDivisores n = d n $ init $ tail $ reverse $ divisores n where d _ [] = [[]] d y (x:xs) | y `mod` x ≡ 0 = map (x:) (d x xs) ⧺ d y xs | otherwise = d y xs divisores :: ℤ → [ℤ] divisores = f ∘ group ∘ primeFactors where f [] = [1] f (xs:xss) = [a × b | a ← f xss, b ← scanl (×) 1 xs] {- > length (cadenasDivisores 123456) 2496 (0.07 secs, 0 bytes) > length (cadenasDivisores 1234567890123456789012) 25988 (2.60 secs, 241,079,064 bytes) -}

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   import Data.List (init, tail, group) import Data.Numbers.Primes   cadenasDivisores :: ℤ → [[ℤ]] cadenasDivisores n = d n $ init $ tail $ reverse $ divisores n   where d _    []  = [[]]         d y (x:xs) | y `mod` x ≡ 0 = map (x:) (d x xs) ⧺ d y xs                    | otherwise     =                     d y xs   divisores :: ℤ → [ℤ] divisores = f ∘ group ∘ primeFactors   where f [] = [1]         f (xs:xss) = [a × b | a ← f xss, b ← scanl (×) 1 xs]   {- > length (cadenasDivisores 123456) 2496 (0.07 secs, 0 bytes) > length (cadenasDivisores 1234567890123456789012) 25988 (2.60 secs, 241,079,064 bytes) -}

   Responder

   1. No, no tiene la misma complejidad, siguiendo la relación de generación saltaríamos la revisión de divisibilidad para toda una secuencia de potenciales divisores (ej. si es n=p q^b con p>q^b ahorraríamos revisar los q, q^2, q^3, … cuando el previo es p). Es decir, aún puede hacerse notablemente más eficiente.

      Responder

   2. Usando la relación de divisibilidad es notablemente más rápido, no obstante, no encuentro una forma de mantener dicha relación y generar las subsecuencias una única vez (sin repetidos), pero creo podría hacerse y evitar el nubOrd (con lo que sería todavía más rápido).

      Haskell

      import Data.List (subsequences) import Data.Numbers.Primes (primeFactors) import Math.Combinat (permuteMultiset) import Data.List.Extra (nubOrd) cadenasDivisores :: ℤ → [[ℤ]] cadenasDivisores = nubOrd -- Sin repetir... ∘ concatMap -- ...obtenemos... ( subsequences -- ...las subsecuencias... ∘ init -- ...sin contar el último elemento... ∘ scanl1 (×)) -- ...manteniendo la relación de divisibilidad... ∘ permuteMultiset -- ...permutando... ∘ primeFactors -- ...todos los factores primos. {- > length (cadenasDivisores 1234567890123456789012) 25988 (1.57 secs, 155,117,088 bytes) -}

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

      import Data.List            (subsequences) import Data.Numbers.Primes  (primeFactors) import Math.Combinat        (permuteMultiset) import Data.List.Extra      (nubOrd)   cadenasDivisores :: ℤ → [[ℤ]] cadenasDivisores = nubOrd            -- Sin repetir...                  ∘ concatMap         -- ...obtenemos...                      ( subsequences  -- ...las subsecuencias...                      ∘ init          -- ...sin contar el último elemento...                      ∘ scanl1 (×))   -- ...manteniendo la relación de divisibilidad...                  ∘ permuteMultiset   -- ...permutando...                  ∘ primeFactors      -- ...todos los factores primos.   {-   > length (cadenasDivisores 1234567890123456789012) 25988 (1.57 secs, 155,117,088 bytes)                  -}

      Responder

3. Haskell

   import Data.List cadenasDivisores :: Int -> [[Int]] cadenasDivisores n = sort $ filter (\xs -> last xs == n && head xs == 1) [xs | xs <- subsequences $ divisores n , verifica xs] verifica :: [Int] -> Bool verifica [] = False verifica [x] = True verifica (x:y:xs) = mod y x == 0 && verifica (y:xs) divisores :: Int -> [Int] divisores n = [x | x <- [1..n], mod n x == 0]

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   import Data.List   cadenasDivisores :: Int -> [[Int]] cadenasDivisores n =     sort     $ filter (\xs -> last xs == n && head xs == 1)              [xs | xs <- subsequences $ divisores n                  , verifica xs]   verifica :: [Int] -> Bool verifica []       = False verifica [x]      = True verifica (x:y:xs) = mod y x == 0 && verifica (y:xs)   divisores :: Int -> [Int] divisores n = [x | x <- [1..n], mod n x == 0]

   Responder