共轭整数分区到位

Question

我正在构建一个包含Partitions类的C++库.我正在尝试实现共轭(下面解释),我无法让它工作.

我的班级成员是:

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向量,我试图避免.

---

根据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 次线性传递来完成：

1. 确定允许执行共轭而不重叠的最小向量大小。
2. 反转原来的分区；因为相对于输入反转的输出允许更少的重叠，因此更少的额外空间。
3. 通过用适当的索引填充向量来执行共轭，重复次数与原始分区中相邻值之间的差异相同。

这是 C++11 实现（另请参阅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);
}

这种实现在某种意义上是到位的。这意味着它使用单个向量并最大限度地减少共轭所需的额外空间。在某些情况下（例如 {4,1,1,1} 或 {4,3,2,1}），仅向向量添加一个额外元素。在困难的情况下（例如 {4,4,4,4}），向量的大小会暂时加倍。

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

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