Division of a double vector into equal parts

Question

Hi,

Any input for a way to split std :: vector into two equal parts? I need to find the smallest possible difference between | part1 - part2 |.

This is how I do it now, but from what you can probably say, in some cases it will not give an optimal split.

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, from highest to lowest, the values ​​can actually be displayed twice. I do not expect part1 and part2 to have the same number of elements, but the sum (part1) should be as close as possible to the sum (part2)

For example, if we had {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 this helps, I am trying to achieve a separation algorithm for encoding Shannon Fano.

, , , http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding#Example

, !

Answer 1

, :

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)

, , , ( -... ). , :

std::pair<std::vector<double>, std::vector<double> >
    split(const std::vector<double>& data)
{
    std::pair<std::vector<double>, std::vector<double> > rv;
    double s1=0.0, s2=0.0;
    std::vector<double>::const_iterator i;

    for (i=data.begin(); i != data.end(); ++i)
    {
        double dif1 = abs(*i + s1 - s2);
        double dif2 = abs(*i + s2 - s1);

        if (dif1 < dif2)
        {
            rv.first.push_back(*i);
            s1 += *i;
        }
        else
        {
            rv.second.push_back(*i);
            s2 += *i;
        }
    }
    return rv;
}

EDIT: , . , , .

Answer 2

, , , NP-Complete, . , . ( " " ).

Answer 3

std- lambdas,

void splitProbabilityVector(std::vector<double>& data, std::vector<double>& rightHandSplit)
{
    double s1=0.0, s2=0.0;
    auto bound = std::stable_partition(data.begin(), data.end(), [&](double e) -> bool
    {
        if (abs(e + s1 - s2) < abs(e + s2 - s1))
        { s1 += e; return true;}
        else
        { s2 += e; return false; }
    });

    rightHandSplit.assign(bound, data.end());
    data.resize(bound-data.begin());
}

. , , wiki, , :

For this reason, Shannon Fano was almost never used; Huffman coding is almost as computationally simple and creates prefix codes that always reach the smallest expected codeword length.