Splitting a double vector into equal parts
- by Cosmin
Greetings,
Any input on a way to divide a std::vector into two equal parts ? I need to find the smallest possible difference between |part1 - part2|.
This is how I'm doing it now, but from what you can probably tell it will yield a non-optimal split in some cases.
auto mid = std::find_if(prim, ultim, [&](double temp) -> bool
{
if(tempsum >= sum)
return true;
tempsum += temp;
sum -= temp;
return false;
});
The vector is sorted, highest to lowest, values can indeed appear twice.
I'm not expecting part1 and part2 to have the same numbers of elements, but sum(part1) should be as close as possible to sum(part2)
For example if we would have { 2.4, 0.12, 1.26, 0.51, 0.70 }, the best split would be { 2.4, 0.12 } and { 1.26, 0.51, 0.70 }.
If it helps, I'm trying to achieve the splitting algorithm for the Shannon Fano encoding.
Any input is appreciated, thanks!
