partitioning of an array
-
Hello,
If have got some Haskell code to convert it in c++. I'm a beginner in c++ and not very common with mathematic algorithms. Here is my problem/code:
import Data.List
import Data.Ord-- search all partitions having n parts of a list xs
-- e.g. partitions [1,2,3,4] 3 should give
-- [[[1],[2],[3,4]],[[1],[2,3],[4]],[[1,2],[3],[4]]]
partitions xs n =
let l = length xs in
let firstParts = map ((flip splitAt) xs) [1.. l - (n - 1)] in
if n == 2
then map (\(l1, l2) -> [l1, l2]) firstParts
else concat $ map (\fp -> map (( : ) (fst fp)) (partitions (snd fp) (n - 1))) firstParts-- the value of a partition is the maximum of the sums of the parts
partitionValue partition = maximum $ map sum partition-- the best partition is the partition with minimum value
bestPartition xs n = minimumBy (comparing partitionValue) $ partitions xs n-- test with 6 stages (11 km -> 16 km -> 5 km -> 5 km -> 12 km -> 10 km) in 3 days
-- result should be [[11],[16,5,5],[12,10]]
main = print $ bestPartition [11, 16, 5, 5, 12, 10] 3It works in HASKELL, but I need to convert it in c++, problem is that it is an exponential algorithm. It works with low stages and days (and will have a stack overflow, when stages/days are a bit higher). I need an algorithm/solution in c++ for higher stages/days. Thanks for your anwer!