Menu Close

Particiones de longitud fija

José A. Alonso,

Definir la función

   particionesFijas :: Int -> Int -> [[Int]]

tal que (particionesFijas n k) es la lista de listas de k números naturales no crecientes cuya suma es n. Por ejemplo,

   ghci> particionesFijas 8 2
   [[4,4],[5,3],[6,2],[7,1]]
   ghci> particionesFijas 8 3
   [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]
   ghci> particionesFijas 9 3
   [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]
   ghci> length (particionesFijas 67 5)
   8056

Soluciones

-- 1ª definición
particionesFijas :: Int -> Int -> [[Int]]
particionesFijas n 1 = [[n]]
particionesFijas n k 
    | k < 1     = []
    | otherwise = [x:y:ys | x <- [1..n-1], 
                            (y:ys) <- particionesFijas (n-x) (k-1),
                            x >= y]
 
-- 2ª definición
particionesFijas2 :: Int -> Int -> [[Int]]
particionesFijas2 n k
    | k <= 0    = []
    | k == 1    = [[n]]
    | k == n    = [replicate k 1]
    | k > n     = []
    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++
                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]
 
-- Comparación:
--    ghci> length (particionesFijas 800 3)
--    53333
--    (1.01 secs, 97696476 bytes)
--    
--    ghci> length (particionesFijas2 800 3)
--    53333
--    (4.52 secs, 693969028 bytes)
Avanzado
, ,

5 soluciones de “Particiones de longitud fija”

  1. Responder
    Paola Cabrera Perza 
    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
  2. Responder
    abrdelrod 
    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))
  3. Responder
    manvermor 
    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]
  4. Responder
    fracruzam 
    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 []     = []
  5. Responder
    manpende 
    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

Escribe tu solución

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