c – 共轭整数分区到位

我正在构建一个包含Partitions类的C库.我试图实现共轭(下面解释)到位,我不能让它工作.

我的班级成员是：

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

例如,整数分区[5,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,1]的缀合物是[4,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;
    }
}

这在很大程度上起作用,但偶尔会覆盖仍然需要的分区的一部分.我正在寻找一种聪明的方式来实现共轭,即不创建新的分区实例.

考虑共轭的另一种方法是认识到缀合物是以下序列

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

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