将双精度向量分成相等的部分

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具有相同数量的元素，但sum(part1)应尽可能接近sum(part2)

例如，如果我们有{2.4,0.12,1.26,0.51,0.70}，最佳拆分将是{2.4,0.12}和{1.26,0.51,0.70}。

如果有帮助的话，我正在尝试实现Shannon Fano编码的拆分算法。

也许这会帮助你们更好地理解我的问题 http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding#Example 感谢任何意见！

- Cosmin

---

尝试扩展您的要求。该描述缺少重要信息，例如分割点是否仅可移动或元素是否也可以从向量的一部分移动到另一部分... - David Rodríguez - dribeas

还有，“|part1-part2|的最小可能差异”是什么意思？我们是在谈论|sum(part1) - sum(part2)|吗？您是否希望part1和part2具有相同数量的元素？ - In silico

可以从part1中选择第1、3和5项，从part2中选择第2和4项吗？ - Matthieu M.

关于如何完全错误地实现简单算法，使用LAMBDA表达式可能会给您带来一些声誉。 - Vicente Botet Escriba

你说向量是从高到低排序的，但在你的例子中并没有。 - Luc Touraille

Answer 1

这是一个被认为是NP-完全的分割问题，因此一般情况下不存在多项式时间算法。但是，当集合中元素的大小受到限制时，该问题变得更容易解决。上述维基百科链接有一个很好的近似算法部分（当你需要一个“足够好”的解决方案时）。

- Kris

Answer 2

假设：

向量已排序，从高到低，值可以重复出现。
我不指望part1和part2具有相同的元素数量，但是
sum(part1)应该尽可能接近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;
}

编辑: 如果您的向量中负数的总和超过了列表中正数的总和，那么这种方法的结果质量会降低。解决方法是尝试按绝对值降序而不是严格降序排序原始列表。

- andand

---

如果查看维基百科条目，这似乎是不正确的：在维基百科条目中，列表已排序（递减），分区涉及在此列表中找到一个分割点，将最高元素放入一个集合中，将最低元素放入另一个集合中...尽管维基百科的示例在这方面似乎不太理想。 - Matthieu M.

这是他们提到并简要描述的贪心算法。 - andand

@Matthieu：这个分割不是一个中心分割，而是数据的分区；元素1和3可以进入子列表1，而元素2和4可以进入子列表2。 - Jamie Cook

Answer 3

如果你想使用标准算法和lambda表达式，你可以按照以下步骤进行。

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

这个算法应该是相当高效的。只是出于好奇，为什么你要使用这个算法，因为在你链接的维基页面上它说：

因此，Shannon-Fano 算法几乎从不使用；Huffman 编码几乎同样计算简单，并且生成的前缀编码总是实现最低期望码字长度。

- Jamie Cook

---

作业是分析一段文本，并比较两种方法得出的结果，计算每种方法的平均编码长度。 - Cosmin

啊！比较……太好了——顺便说一下，我喜欢你在问题示例代码中使用了C++0x。 - Jamie Cook