# 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] 3

It 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!