Árbol de subconjuntos

5 Comentarios

1. Haskell

   import Data.List import Test.QuickCheck data Arbol = N [Int] [Arbol] deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs = N xs (map arbolSubconjuntos (subconjuntosMaximales xs)) subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs = [as | as <- reverse (subsequences xs) , length as == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos n xs = nOcurrencias n (arbolSubconjuntos xs) nOcurrencias :: [Int] -> Arbol -> Int nOcurrencias xs (N ys []) | iguales xs ys = 1 | otherwise = 0 nOcurrencias xs (N ys zss) | iguales xs ys = 1 + sum [nOcurrencias xs zs | zs <- zss] | otherwise = sum [nOcurrencias xs zs | zs <- zss] subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = and [elem x ys | x <- xs] iguales :: Eq a => [a] -> [a] -> Bool iguales xs ys = subconjunto xs ys && subconjunto ys xs prop_nOcurrenciasArbolSubconjuntos :: Int -> Int -> Property prop_nOcurrenciasArbolSubconjuntos k n = k < n && k > 0 && n > 0 ==> nOcurrenciasArbolSubconjuntos [1..k] [1..n] == factorial (n-k) factorial :: Int -> Int factorial n = product [1..n] -- La comprobación es: -- λ> quickCheckWith (stdArgs {maxSize=8}) prop_nOcurrenciasArbolSubconjuntos -- *** Gave up! Passed only 60 tests.

   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

   import Data.List import Test.QuickCheck data Arbol = N [Int] [Arbol]      deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs =   N xs (map arbolSubconjuntos (subconjuntosMaximales xs)) subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs =   [as | as <- reverse (subsequences xs)       , length as == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos n xs =   nOcurrencias n (arbolSubconjuntos xs) nOcurrencias :: [Int] -> Arbol -> Int nOcurrencias xs (N ys [])   | iguales xs ys = 1   | otherwise     = 0 nOcurrencias xs (N ys zss)   | iguales xs ys = 1 + sum [nOcurrencias xs zs | zs <- zss]   | otherwise     = sum [nOcurrencias xs zs | zs <- zss]   subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = and [elem x ys | x <- xs] iguales :: Eq a => [a] -> [a] -> Bool iguales xs ys = subconjunto xs ys &&  subconjunto ys xs prop_nOcurrenciasArbolSubconjuntos :: Int -> Int -> Property prop_nOcurrenciasArbolSubconjuntos k n =   k < n && k > 0 && n > 0 ==>    nOcurrenciasArbolSubconjuntos [1..k] [1..n] == factorial (n-k)     factorial :: Int -> Int factorial n = product [1..n] -- La comprobación es: -- λ> quickCheckWith (stdArgs {maxSize=8}) prop_nOcurrenciasArbolSubconjuntos -- *** Gave up! Passed only 60 tests.

   Responder

2. Haskell

   import Data.List import Test.QuickCheck data Arbol = N [Int] [Arbol] deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs = N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs] subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs = filter f (subsequences xs) where f ys = length ys == length xs-1 nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos xs = length . filter (igual xs) . (pliega . arbolSubconjuntos) pliega :: Arbol -> [[Int]] pliega (N [] []) = [[]] pliega (N xs ys) = xs : concat (map pliega ys) igual :: [Int] -> [Int] -> Bool igual xs ys = sort xs == sort ys prop_ocurrencias :: Int -> Int -> Bool prop_ocurrencias k n = nOcurrenciasArbolSubconjuntos [1..a] [1..b] == product [1..b-a] where a = min (abs k) (abs n) b = max (abs k) (abs n)

   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

   import Data.List import Test.QuickCheck data Arbol = N [Int] [Arbol]      deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs =   N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs] subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs = filter f (subsequences xs)   where f ys = length ys == length xs-1 nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos xs =   length . filter (igual xs) . (pliega . arbolSubconjuntos) pliega :: Arbol -> [[Int]] pliega (N [] []) = [[]] pliega (N xs ys) = xs : concat (map pliega ys) igual :: [Int] -> [Int] -> Bool igual xs ys = sort xs == sort ys prop_ocurrencias :: Int -> Int -> Bool prop_ocurrencias k n =    nOcurrenciasArbolSubconjuntos [1..a] [1..b] == product [1..b-a]    where a = min (abs k) (abs n)          b = max (abs k) (abs n)

   Responder

3. Haskell

   import Data.List (subsequences) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs = N xs [arbolSubconjuntos ys | ys <- subsequences xs , length ys == length xs - 1] arbolSubconjuntos [_] = N [] [] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos xs ys = aux xs (arbolSubconjuntos ys) where aux xs (N zs xss) | iguales xs zs = 1 + sum [aux xs os | os <- xss] | otherwise = sum [aux xs os | os <- xss] aux xs (N [] [] ) | null xs = 1 | otherwise = 0 contenido xs ys = and [elem x ys | x <- xs] iguales xs ys = contenido xs ys && contenido ys xs prop_arbolSubconjuntos :: Int -> [Int] -> Property prop_arbolSubconjuntos n xs = n > 0 && contenido xs [1..n] && nub xs == xs ==> nOcurrenciasArbolSubconjuntos xs [1..n] == product[1..n - length xs] where contenido xs ys = and [elem x ys | x <- xs]

   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

   import Data.List (subsequences)   arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs =   N xs [arbolSubconjuntos ys | ys <- subsequences xs                                , length ys == length xs - 1] arbolSubconjuntos [_] = N [] []   nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos xs ys =   aux xs (arbolSubconjuntos ys)   where aux xs (N zs xss)           | iguales xs zs = 1 + sum [aux xs os | os <- xss]           | otherwise     =     sum [aux xs os | os <- xss]         aux xs (N [] [] )           | null xs   = 1           | otherwise = 0         contenido xs ys = and [elem x ys | x <- xs]         iguales xs ys = contenido xs ys &&  contenido ys xs   prop_arbolSubconjuntos :: Int -> [Int] -> Property prop_arbolSubconjuntos n xs  =   n > 0 && contenido xs [1..n] && nub xs == xs ==>   nOcurrenciasArbolSubconjuntos xs [1..n] == product[1..n - length xs]   where contenido xs ys = and [elem x ys | x <- xs]

   Responder

4. Haskell

   import Data.List (subsequences) import Test.QuickCheck data Arbol = N [Int] [Arbol] deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs = N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs] subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs = [ys | ys <- subsequences xs, length ys == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos ys xs | xs == ys = 1 | otherwise = nOcurrencias ys (arbolSubconjuntos xs) nOcurrencias :: [Int] -> Arbol -> Int nOcurrencias ys (N xs zss) | iguales ys xs = 1 + sum [nOcurrencias ys zs | zs <- zss] | otherwise = sum [nOcurrencias ys zs | zs <- zss] subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs iguales :: Eq a => [a] -> [a] -> Bool iguales xs ys = subconjunto xs ys && subconjunto ys xs prop_subconjunto :: Int -> [Int] -> Property prop_subconjunto n xs = elem xs (subsequences [1..n]) && n > 0 ==> nOcurrenciasArbolSubconjuntos xs [1..n] == factorial (n- length xs) factorial :: Int -> Int factorial x = product [1..x]

   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

   import Data.List (subsequences) import Test.QuickCheck   data Arbol = N [Int] [Arbol]   deriving (Eq, Show)   arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs =   N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs]   subconjuntosMaximales :: [Int] -> [[Int]] subconjuntosMaximales xs =   [ys | ys <- subsequences xs, length ys == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos ys xs | xs == ys  = 1 | otherwise = nOcurrencias ys (arbolSubconjuntos xs)   nOcurrencias :: [Int] -> Arbol -> Int nOcurrencias ys (N xs zss)   | iguales ys xs = 1 + sum [nOcurrencias ys zs | zs <- zss]   | otherwise     = sum [nOcurrencias ys zs | zs <- zss]   subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs   iguales :: Eq a => [a] -> [a] -> Bool iguales xs ys = subconjunto xs ys &&  subconjunto ys xs prop_subconjunto :: Int -> [Int] -> Property prop_subconjunto n xs =   elem xs (subsequences [1..n]) && n > 0 ==>   nOcurrenciasArbolSubconjuntos xs [1..n] == factorial (n- length xs)   factorial :: Int -> Int factorial x = product [1..x]

   Responder

5. Haskell

   import Data.List (permutations, subsequences) import Test.QuickCheck data Arbol = N [Int] [Arbol] deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs = N xs (map arbolSubconjuntos (maximales xs)) maximales :: [Int] -> [[Int]] maximales xs = reverse [ys | ys <- subsequences xs, length ys == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos ys xs = aparece ys (todos xs) aparece :: [Int] -> [[Int]] -> Int aparece ys [] = 0 aparece ys (xs:xss) | ys == xs = 1 + aparece ys xss | otherwise = aparece ys xss todos :: [Int] -> [[Int]] todos xs = [ys | ys <- concat (todosmaximales [xs]), length ys < 2] ++ permutaciones [xs] ++ permutations xs todosmaximales :: [[Int]] ->[[[Int]]] todosmaximales [] = [] todosmaximales xss = map maximales xss ++ todosmaximales (concat (map maximales xss)) permutaciones :: [[Int]] -> [[Int]] permutaciones xss = concat [permutations ys | ys <- [xs | xs <- concat (todosmaximales xss) , length xs > 1]] prop_arbolSubconjuntos :: Int -> Property prop_arbolSubconjuntos n = n > 0 ==> and [ nOcurrenciasArbolSubconjuntos ys [1..n] == product [1..n - length ys] | ys <- todos [1..n]] -- λ> quickCheckWith (stdArgs {maxSize=6}) prop_arbolSubconjuntos -- +++ OK, passed 100 tests.

   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

   import Data.List (permutations, subsequences) import Test.QuickCheck   data Arbol = N [Int] [Arbol]   deriving (Eq, Show) arbolSubconjuntos :: [Int] -> Arbol arbolSubconjuntos xs =   N xs (map arbolSubconjuntos (maximales xs)) maximales :: [Int] -> [[Int]] maximales xs =   reverse [ys | ys <- subsequences xs, length ys == length xs - 1] nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int nOcurrenciasArbolSubconjuntos ys xs = aparece ys (todos xs) aparece :: [Int] -> [[Int]] -> Int aparece ys [] = 0 aparece ys (xs:xss)   | ys == xs  = 1 + aparece ys xss   | otherwise = aparece ys xss todos :: [Int] -> [[Int]] todos xs = [ys | ys <- concat (todosmaximales [xs]), length ys < 2]            ++ permutaciones [xs]            ++ permutations xs todosmaximales :: [[Int]] ->[[[Int]]] todosmaximales [] = [] todosmaximales xss =   map maximales xss ++ todosmaximales (concat (map maximales xss)) permutaciones :: [[Int]] -> [[Int]] permutaciones xss =   concat [permutations ys          | ys <- [xs | xs <- concat (todosmaximales xss)                      , length xs > 1]] prop_arbolSubconjuntos :: Int -> Property prop_arbolSubconjuntos n  =   n > 0 ==>   and [ nOcurrenciasArbolSubconjuntos ys [1..n] ==         product [1..n - length ys]       | ys <- todos [1..n]] --   λ> quickCheckWith (stdArgs {maxSize=6}) prop_arbolSubconjuntos --   +++ OK, passed 100 tests.

   Responder