Ordered partitions: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,193: / Line 1,193: @@
 Faster by keeping track of the length of lists:
-<lang haskell>-- choose m out of n items, return tuple of chosen and the rest
+<lang haskell>import Data.Bifunctor (first, second)
-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 _ _ [] = [[]]
+choose [] _ _ = [([], [])]
-	combos s n (x:xs) = [ l : r |	(l,rest) <- choose s n x,
-					r <- combos rest (n - x) xs]
+choose aa _ 0 = [([], aa)]
+choose aa@(a : as) n m
+  | n == m = [(aa, [])]
+  | otherwise =
+    (first (a :) <$> choose as (n - 1) (m - 1))
+      <> (second (a :) <$> choose as (n - 1) m)
+partitions :: [Int] -> [[[Int]]]
+partitions x = combos [1 .. n] n x
+  where
+    n = sum x
+    combos _ _ [] = [[]]
+    combos s n (x : xs) =
+      [ l : r
+        | (l, rest) <- choose s n x,
+          r <- combos rest (n - x) xs
+      ]
+main :: IO ()
-main = mapM_ print $ partitions [5,5,5]</lang>
+main = mapM_ print $ partitions [5, 5, 5]</lang>
 =={{header|J}}==