Particiones de longitud fija

5 Comentarios

1. Haskell

   import Data.List particionesFijas k n = [reverse(xs)|xs<-(subsecuencias3 k n),sum xs==k] repiteElementos1 :: Int -> [t] -> [t] repiteElementos1 n []=[] repiteElementos1 n xs = concatMap (replicate n) xs subsecuencias2 :: (Enum a, Eq a, Num a) => a -> Int -> [[a]] subsecuencias2 k n = nub(filter(longitud n)(subsequences([1..k]++(repiteElementos1 n [1..(k-1)])))) subsecuencias3 :: (Enum a, Num a, Ord a) => a -> Int -> [[a]] subsecuencias3 0 n = [replicate n 0] subsecuencias3 k 0=[[]] subsecuencias3 k 1=[[k]] subsecuencias3 k n =nub[sort xs|xs<-(subsecuencias2 (k-1) n)] longitud :: Foldable t => Int -> t a -> Bool longitud n xs = length xs == n

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

   import Data.List particionesFijas k n = [reverse(xs)|xs<-(subsecuencias3 k n),sum xs==k]                               repiteElementos1 :: Int -> [t] -> [t] repiteElementos1 n []=[] repiteElementos1 n xs = concatMap (replicate n) xs subsecuencias2 :: (Enum a, Eq a, Num a) => a -> Int -> [[a]] subsecuencias2 k n = nub(filter(longitud n)(subsequences([1..k]++(repiteElementos1 n [1..(k-1)])))) subsecuencias3 :: (Enum a, Num a, Ord a) => a -> Int -> [[a]] subsecuencias3 0 n = [replicate n 0] subsecuencias3 k 0=[[]] subsecuencias3 k 1=[[k]] subsecuencias3 k n =nub[sort xs|xs<-(subsecuencias2 (k-1) n)] longitud :: Foldable t => Int -> t a -> Bool longitud n xs = length xs == n

   Responder

2. Haskell

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n 1 = [[n]] particionesFijas n 2 = [[x,n-x] | x <- [div n 2 + if odd n then 1 else 0..n-1]] particionesFijas n k = concatMap aux [1..n-1] where aux m = filter (\(x:y:_) -> x >= y) $ map (m:) (particionesFijas (n-m) (k-1))

   1 2 3 4 5

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n 1 = [[n]] particionesFijas n 2 = [[x,n-x] | x <- [div n 2 + if odd n then 1 else 0..n-1]] particionesFijas n k = concatMap aux [1..n-1]     where aux m =  filter (\(x:y:_) -> x >= y) $ map (m:) (particionesFijas (n-m) (k-1))

   Responder

3. Haskell

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n 1 = [[n]] particionesFijas n k = [ x:y:xs | x <- [1..n-1], (y:xs) <-particionesFijas (n-x) (k-1), y <= x]

   1 2 3 4

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n 1 = [[n]] particionesFijas n k =   [ x:y:xs | x <- [1..n-1], (y:xs) <-particionesFijas (n-x) (k-1), y <= x]

   Responder

4. Haskell

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n m | m > n = error "No es posible encontrar una partición de tal dimensión" | otherwise = busca [(m,replicate m 1)] where busca :: [(Int,[Int])] -> [[Int]] busca ((s,xs):xss) | s == n && decreciente xs = xs: busca xss | s == n = busca xss | otherwise = busca (xss ++ yss) where yss = [par | ys <- suma1 xs, let par = (s+1,ys), par `notElem` xss] busca [] = [] decreciente :: [Int] -> Bool decreciente (x:ys@(y:_)) = x >= y && decreciente ys decreciente _ = True suma1 :: [Int] -> [[Int]] suma1 (x:xs) = ((x+1):xs): (map (x:) $ suma1 xs) suma1 [] = []

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

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n m     | m > n     = error "No es posible encontrar una partición de tal dimensión"     | otherwise = busca [(m,replicate m 1)]   where busca :: [(Int,[Int])] -> [[Int]]         busca ((s,xs):xss)           | s == n && decreciente xs = xs: busca xss           | s == n                   = busca xss           | otherwise                = busca (xss ++ yss)           where yss =  [par | ys <- suma1 xs, let par = (s+1,ys), par `notElem` xss]         busca []         = []         decreciente :: [Int] -> Bool         decreciente (x:ys@(y:_)) = x >= y && decreciente ys         decreciente  _           = True         suma1 :: [Int] -> [[Int]]         suma1 (x:xs) = ((x+1):xs): (map (x:) $ suma1 xs)         suma1 []     = []

   Responder

5. Haskell

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n k = concat [map (++ [m]) (particionesFijasAux m (n-m)(k-1)) | m <- [1..x]] where x = div n k particionesFijasAux :: Int -> Int -> Int -> [[Int]] particionesFijasAux _ n 1 = [[n]] particionesFijasAux x n k = concat [map (++ [m]) (particionesFijasAux m (n-m) (k-1)) | m <- [x..y]] where y = div n k

   1 2 3 4 5 6 7 8 9 10

   particionesFijas :: Int -> Int -> [[Int]] particionesFijas n k = concat [map (++ [m])        (particionesFijasAux m (n-m)(k-1)) | m <- [1..x]]          where x = div n k   particionesFijasAux :: Int -> Int -> Int -> [[Int]] particionesFijasAux _ n 1 = [[n]] particionesFijasAux x n k = concat [map (++ [m])        (particionesFijasAux m (n-m) (k-1)) | m <- [x..y]]            where y = div n k

   Responder