conjugate integer partitions in place

Question

I'm building a C++ library that includes a Partitions class. I'm trying to implement conjugation (explained below) in place, and I cannot get it to work.

My class members are:

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

As an example, the integer partition [5,4,4,1] has

_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

If the partition is [m_1,m_2,...,m_k], then the conjugate is [n_1,n_2,...,n_l] where

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

For example, the conjugate of [5,4,4,1] is [4,3,3,3,1]. Another way to see this is to draw the partition as rows of unit squares where the number of squares in the ith row is m_i. Reading the heights of the columns then gives the conjugate. For the same example, the picture is

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

The math translated into the programming syntax as m_i = _parts[i-1] and k = _length. Here's a broken implementation for conjugation:

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

This works much of the time, but occasionally it overwrites part of the partition that is still needed. I'm looking for a clever way to do the conjugation in place, i.e. without creating a new instance of Partition.

One other way to think of conjugation is to realize that the conjugate is the following sequence

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

Using this idea, I have the following implementation that gives the correct answer:

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

However, it uses another std vector, which I am trying to avoid.

---

In line with Evgeny Kluev's answer (accepted below), here's the final code that works (see his answer for details):

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

This could be done in 3 linear passes:

1. Determine minimal vector size that allows to perform conjugation without overlapping.
2. Reverse original partition; since output reversed relative to input allows less overlapping and therefore less additional space.
3. Perform conjugation by filling vector with appropriate indices repeated as many times as is a difference between adjacent values in the original partition.

Here is C++11 implementation (see also 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);
}

This implementation is in-place in some sense. Meaning that it uses single vector and minimizes extra space needed for conjugation. In some cases (like {4,1,1,1} or {4,3,2,1}) only one extra element is added to the vector. In difficult cases (like {4,4,4,4}) size of the vector temporarily doubles.

It is possible to use this approach without using too much extra space. Since "bad" cases like {4,4,4,4} obviously have very low entropy we could compress original partition. However this would complicate the code.

Combination of RLE and delta encoding makes this algorithm truly in-place (which means O(1) additional space). Use positive numbers (or zero high bit) to encode differences between adjacent values in the original partition (as conjugation step needs only differences anyway). Use negative numbers (or nonzero high bit) to encode runs of zero (remaining bits of the number tell how many zeros). All this limits delta value and zero counter to half the range. But in both cases there may be at most one value exceeding half the range. So we could just prefix this oversized value with a zero (and reserve space in the vector for at most 2 such zeros).