Разбиение двойного вектора на равные части

Question

Привет,

Есть ли какие-либо данные о способе деления std :: vector на две равные части? Мне нужно найти наименьшую возможную разницу между | part1 - part2 |.

Вот как я это делаю сейчас, но из того, что вы, вероятно, можете сказать, это приведет к неоптимальному разделению в некоторых случаях.

auto mid = std::find_if(prim, ultim, [&](double temp) -> bool
{
    if(tempsum >= sum)
        return true;

    tempsum += temp;
    sum -= temp;
    return false;
});

Вектор отсортирован по убыванию, значения могут отображаться дважды. Я не ожидаю, что part1 и part2 будут иметь одинаковое количество элементов, но сумма (часть1) должна быть как можно ближе к сумме (часть2)

Например, если бы у нас было {2,4, 0,12, 1,26, 0,51, 0,70}, наилучшим разделением было бы {2,4, 0,12} и {1,26, 0,51, 0,70}.

Если это поможет, я пытаюсь реализовать алгоритм расщепления для кодирования Шеннона Фано.

Может быть, это поможет вам лучше понять мой вопрос http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding#Example

Любой вклад приветствуется, спасибо!

Answer 1

Это проблема разбиения , которая, как известно, является NP-полной, так что алгоритм полиномиального времени вообще не существует. Однако проблема становится легче, когда размеры элементов в наборе ограничены. Выше ссылка на Википедию имеет довольно хороший раздел об алгоритмах аппроксимации (когда вам нужно «достаточно хорошее» решение).

Answer 2

Учитывая, что:

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;
}

РЕДАКТИРОВАТЬ: При таком подходе качество результата будет ниже, если сумма отрицательных чисел в вашем векторе превосходит сумму положительных чисел в списке. Чтобы решить эту проблему, можно попытаться упорядочить исходный список по убыванию абсолютного значения, а не в строго убывающем порядке.

Answer 3

Если вы хотите использовать стандартные алгоритмы и лямбда-выражения, вы можете сделать следующее

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());
}

, который должен быть довольно производительным. Просто из любопытства, почему вы используете этот алгоритм, когда на вики-странице, с которой вы связались, написано:

По этой причине Шеннон-Фано почти никогда не используется; Кодирование Хаффмана почти так же прост в вычислительном отношении и создает префиксные коды, которые всегда достичь наименьшего ожидаемого кодового слова длина.