Ordered partitions: Difference between revisions
m
→{{header|Haskell}}: Tidied (applied Ormolu and Hlint to last example)
m (→{{header|Haskell}}: Tidied (applied Ormolu and Hlint to last example)) |
|||
Line 1,193:
Faster by keeping track of the length of lists:
<lang haskell>
choose aa _ 0 = [([], aa)]▼
choose aa@(a:as) n m▼
| n == m = [(aa, [])]▼
| otherwise = map (\(x,y) -> (a:x, y)) (choose as (n-1) (m-1)) ++▼
map (\(x,y) -> (x, a:y)) (choose as (n-1) m)▼
-- choose m out of n items, return tuple of chosen and the rest
partitions x = combos [1..n] n x where▼
n = sum x▼
choose :: [Int] -> Int -> Int -> [([Int], [Int])]
combos _ _ [] = [[]]▼
combos s n (x:xs) = [ l : r | (l,rest) <- choose s n x,▼
▲choose aa@(a : as) n m
| otherwise =
partitions :: [Int] -> [[[Int]]]
where
combos s n (x : xs) =
[ l : r
r <- combos rest (n - x) xs
]
main :: IO ()
main = mapM_ print $ partitions [5, 5, 5]</lang>
=={{header|J}}==
| |||