Menu Close

Subconjuntos divisibles

Definir la función

  subconjuntosDivisibles :: [Int] -> [[Int]]

tal que (subconjuntosDivisibles xs) es la lista de todos los subconjuntos de xs en los que todos los elementos tienen un factor común mayor que 1. Por ejemplo,

  subconjuntosDivisibles []         ==  [[]]
  subconjuntosDivisibles [1]        ==  [[]]
  subconjuntosDivisibles [3]        ==  [[3],[]]
  subconjuntosDivisibles [1,3]      ==  [[3],[]]
  subconjuntosDivisibles [3,6]      ==  [[3,6],[3],[6],[]]
  subconjuntosDivisibles [1,3,6]    ==  [[3,6],[3],[6],[]]
  subconjuntosDivisibles [2,3,6]    ==  [[2,6],[2],[3,6],[3],[6],[]]
  subconjuntosDivisibles [2,3,6,8]  ==  [[2,6,8],[2,6],[2,8],[2],[3,6],[3],[6,8],[6],[8],[]]
  length (subconjuntosDivisibles [1..10])  ==  41
  length (subconjuntosDivisibles [1..20])  ==  1097
  length (subconjuntosDivisibles [1..30])  ==  33833
  length (subconjuntosDivisibles [1..40])  ==  1056986

Soluciones

import Data.List (foldl1', subsequences)
 
-- 1ª solución
-- ===========
 
subconjuntosDivisibles :: [Int] -> [[Int]]
subconjuntosDivisibles xs = filter esDivisible (subsequences xs)
 
-- (esDivisible xs) se verifica si todos los elementos de xs tienen un
-- factor común mayor que 1. Por ejemplo,
--    esDivisible [6,10,22]  ==  True
--    esDivisible [6,10,23]  ==  False
esDivisible :: [Int] -> Bool
esDivisible [] = True
esDivisible xs = mcd xs > 1
 
-- (mcd xs) es el máximo común divisor de xs. Por ejemplo,
--    mcd [6,10,22]  ==  2
--    mcd [6,10,23]  ==  1
mcd :: [Int] -> Int
mcd = foldl1' gcd
 
-- 2ª solución
-- ===========
 
subconjuntosDivisibles2 :: [Int] -> [[Int]]
subconjuntosDivisibles2 []     = [[]]
subconjuntosDivisibles2 (x:xs) = [x:ys | ys <- yss, esDivisible (x:ys)] ++ yss
  where yss = subconjuntosDivisibles2 xs
 
-- 3ª solución
-- ===========
 
subconjuntosDivisibles3 :: [Int] -> [[Int]]
subconjuntosDivisibles3 []     = [[]]
subconjuntosDivisibles3 (x:xs) = filter esDivisible (map (x:) yss) ++ yss
  where yss = subconjuntosDivisibles3 xs
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (subconjuntosDivisibles [1..21])
--    1164
--    (3.83 secs, 5,750,416,768 bytes)
--    λ> length (subconjuntosDivisibles2 [1..21])
--    1164
--    (0.01 secs, 5,400,232 bytes)
--    λ> length (subconjuntosDivisibles3 [1..21])
--    1164
--    (0.01 secs, 5,264,928 bytes)
--    
--    λ> length (subconjuntosDivisibles2 [1..40])
--    1056986
--    (6.95 secs, 8,845,664,672 bytes)
--    λ> length (subconjuntosDivisibles3 [1..40])
--    1056986
--    (6.74 secs, 8,727,141,792 bytes)

Pensamiento

Abejas, cantores,
no a la miel, sino a las flores.

Antonio Machado

6 soluciones de “Subconjuntos divisibles

  1. luipromor
    import Data.List (nub)
     
    subconjuntosDivisibles :: [Int] -> [[Int]]
    subconjuntosDivisibles = nub . map nub . subconjuntosDivisibles1
     
    subconjuntosDivisibles1 :: [Int] -> [[Int]]
    subconjuntosDivisibles1 []     = [[]]
    subconjuntosDivisibles1 (x:xs) = yss ++ [x:ys | ys <- yss, f x ys]
      where yss = subconjuntosDivisibles1 xs
            f x ys | x == 1    = False
                   | null ys   = True
                   | otherwise = all (n -> gcd x n > 1) ys
  2. frahidzam
    subconjuntosDivisibles :: [Int] -> [[Int]]
    subconjuntosDivisibles [] = [[]]
    subconjuntosDivisibles (x:ys)
      | x /= 1    = [x:as | as <- subconjuntosDivisibles ys, maxDiv (x:as) /= 1] 
                    ++ subconjuntosDivisibles ys
      | otherwise = subconjuntosDivisibles ys
     
    maxDiv :: [Int] -> Int
    maxDiv = foldl1 gcd
  3. javmarcha1
    import Data.Numbers.Primes
    import Data.List
     
    -- Proporciona el mismo resultado que los ejemplos pero en distinto orden
     
    subconjuntosDivisibles :: [Int] -> [[Int]]
    subconjuntosDivisibles [] = [[]]
    subconjuntosDivisibles [1] = [[]] 
    subconjuntosDivisibles xs | eliminados xs == [] = []:((subs xss)(subs yss))
                              | otherwise = []: eliminados xs ++((subs xss)(subs yss))
      where subs zss = subsecuencias zss
            xss = gruposSegunFactorComun xs
            yss = intersecciones xs
     
    subsecuencias:: [[Int]] -> [[Int]]
    subsecuencias xss = concat[tail(subsequences ys) | ys <- xss]
     
    gruposSegunFactorComun :: [Int] -> [[Int]]
    gruposSegunFactorComun xs = [numerosConFactorComun x xs |
                           x <- (take (posicionPrimoMayor xs) primes)]
      where numerosConFactorComun a as =
              [b | (c,b) <- (numerosConUnFactor as), c==a]
            numerosConUnFactor ds = [(d,e) |
              d <- (take (posicionPrimoMayor ds) primes),
              (e,es) <- (numeroFactores ds), elem d es]
            posicionPrimoMayor fs = fst(head[(g,h) |
              f <- [(maximum fs),((maximum fs)-1)..2],
              isPrime f, (g,h) <- zip [1..(maximum fs)] primes, f ==h])
            numeroFactores js = [(j,primeFactors j) | j <- js]
     
    intersecciones :: [Int] -> [[Int]]
    intersecciones xs = nub[intersect zs ys | zs <- d,ys <- d,
                        zs /= ys,intersect zs ys /= []]
      where d = gruposSegunFactorComun xs
     
    eliminados :: [Int] -> [[Int]]
    eliminados xs = [[x] | x <- (nub ys), (aparece x ys) >= (aparece x zs)]
      where ys = concat(intersecciones xs)
            zs = concat(gruposSegunFactorComun xs)
            aparece a bs = length[b | b <- bs, b==a]
  4. luipromor
    subconjuntosDivisibles [] = [[]]
    subconjuntosDivisibles (x:xs) = yss ++ [x:ys | ys <- yss, f x ys]
      where yss = subconjuntosDivisibles xs
            f x ys | x == 1    = False
                   | null ys   = True
                   | otherwise = foldl1 gcd (x:ys) > 1
  5. adogargon
    import Data.List (subsequences)
     
    subconjuntosDivisibles :: [Int] -> [[Int]]
    subconjuntosDivisibles xs = filter (xs -> mcd xs /= 1 ) $! subsequences xs
     
    mcd :: [ Int ] -> Int
    mcd [] = 0 
    mcd xs = foldl1 gcd xs
  6. danmorper2
    subconjuntosDivisibles :: [Int] -> [[Int]]
    subconjuntosDivisibles xs = ole (subsequences xs)
     
    ole :: [[Int]] -> [[Int]]
    ole [] = []
    ole (ys:yss) | null ys       = ys:ole yss
                 | arsa ys==True = ys:ole yss
                 | otherwise     = ole yss
     
    arsa :: [Int] -> Bool
    arsa xs = ok xs (factorizar (head xs))
     
    ok :: [Int] -> [Int] -> Bool
    ok _ []      = False
    ok xs (p:ps) = all (==0) [rem y p | y <- ys] || ok xs ps
      where ys = tail xs
     
    factorizar :: Int -> [Int]  
    factorizar n = [x | x <- [1..n], primo x, rem n x == 0]
     
    primo :: Int -> Bool 
    primo n = length [x | x <- [1..n], rem n x == 0] == 2

Escribe tu solución

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