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!


Log in to reply