c++ - 就地共轭整数分区

Question

我正在构建一个包含分区类的 C++ 库。我正在尝试就地实现接合(如下所述)，但我无法让它发挥作用。

我的类(class)成员是:

size_t _size;
size_t _length;
std::vector<int> _parts;

例如，整数分区[5,4,4,1]有

_size = 14   // 5 + 4 + 4 + 1
_length = 4  // 4 nonzero parts
_parts[0] = 5
_parts[1] = 4
_parts[2] = 4
_parts[3] = 1 
_parts[i] = junk // i>3

如果分区是[m_1,m_2,...,m_k]，则共轭是[n_1,n_2,...,n_l] 其中

l = m_1 // length and the first part are switched
n_i = sum{ m_j | m_j > i}

例如，[5,4,4,1] 的共轭是[4,3,3,3,1]。另一种查看方式是将分区绘制为单位正方形的行，其中第 i 行中的正方形数量为 m_i。读取列的高度然后给出共轭。同样的例子，图片是

1| x
4| x x x x
4| x x x x
5| x x x x x
  __________
   4 3 3 3 1

数学转换为编程语法为 m_i = _parts[i-1] 和 k = _length。这是一个错误的共轭实现:

void
Partition::conjugate() {
    size_t k = _length;
    _length = _parts[0];
    int newPart;
    for (int i=(int)_length; i>0; --i) {
        newPart = 0;
        for (int j=0; j<k; ++j) {
            if (_parts[j] >= i) newPart++;
            else break;
        }
        _parts[i-1] = newPart;
    }
}

这在大部分时间都有效，但偶尔会覆盖仍然需要的部分分区。我正在寻找一种巧妙的方法来就地进行共轭，即不创建 Partition 的新实例。

另一种思考共轭的方法是认识到共轭是以下序列

k...k   (k-1)...(k-1)   ...   1...1
x m_k   x(m_(k-1)-m_k)      x(m_1 - m_2)

使用这个想法，我有以下给出正确答案的实现:

void
Partition::conjugate() {
    if (_length == _size) {
        this->first();
        return;
    } else if (_length == 1) {
        this->last();
        return;
    }

    std::vector<int> diffs;
    diffs.push_back(_parts[_length-1]);
    for (size_t i=_length-1; i>0; --i)
        diffs.push_back(_parts[i-1]-_parts[i]);

    size_t pos = 0;
    for (int i=0; i<_length; ++i) {
        for (int j = diffs[i]; j>0; --j)
            _parts[pos++] = (int)_length - i;
    }
    _length = pos;
}

但是，它使用了另一个我试图避免的 std vector 。

---

根据 Evgeny Kluev 的回答(在下面接受)，这里是最终有效的代码(详情请参阅他的回答):

void
Partition::conjugate() {
    if (_length == _size) {
        this->first();
        return;
    } else if (_length == 1) {
        this->last();
        return;
    }

    int last = _parts[_length-1];
    for (int i=1; i<_length; ++i)
        _parts[_size-i] = _parts[i-1] - _parts[i];
    size_t pos = 0;
    for (int i=0; i<last; ++i)
        _parts[pos++] = (int)_length;
    for (int i=1; i<_length; ++i) {
        for (int j = _parts[_size-_length+i]; j>0; --j)
            _parts[pos++] = (int)_length - i;
    }
    _length = pos;
}

Answer 1

这可以在 3 个线性 channel 中完成:

1. 确定允许在不重叠的情况下进行结合的最小载体大小。
2. 反转原始分区；由于输出相对于输入颠倒允许更少的重叠，因此更少的额外空间。
3. 通过使用适当的索引填充 vector 来执行共轭，重复次数与原始分区中相邻值之间的差异相同。

这里是 C++11 实现(另见 complete program on Ideone )。

void conjugate()
{
    size_t space = 0;
    for (size_t i = 0; i < _length; ++i)
        space = max(space, _parts[i] + i);
    ++space;

    _parts.resize(space);
    reverse(begin(_parts), end(_parts));

    auto it_out = begin(_parts);
    auto it_in = end(_parts) - _length;
    size_t prev = 0;

    for (; it_in < end(_parts); ++it_in)
    {
        it_out = fill_n(it_out, *it_in - prev, end(_parts) - it_in);
        prev = *it_in;
    }

    _length = it_out - begin(_parts);
    _parts.resize(_length);
}

这个实现在某种意义上是就地的。这意味着它使用单个 vector 并最大限度地减少缀合所需的额外空间。在某些情况下(如 {4,1,1,1} 或 {4,3,2,1})只有一个额外的元素被添加到 vector 中。在困难的情况下(如 {4,4,4,4})， vector 的大小会暂时加倍。

可以在不使用太多额外空间的情况下使用这种方法。由于像 {4,4,4,4} 这样的“坏”情况显然具有非常低的熵，我们可以压缩原始分区。然而，这会使代码复杂化。

RLE 和增量编码的结合使该算法真正就地(这意味着 O(1) 额外空间)。使用正数(或零高位)对原始分区中相邻值之间的差异进行编码(因为共轭步骤无论如何只需要差异)。使用负数(或非零高位)对零的运行进行编码(数字的剩余位表示有多少个零)。所有这些都将 delta 值和零计数器限制在范围的一半。但在这两种情况下，最多可能有一个值超过范围的一半。所以我们可以在这个过大的值前面加上一个零(并在 vector 中为最多 2 个这样的零保留空间)。