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).

Answer 2

input array in[] = [1,4,4,5],assume in[i]>=i+1(if it's not, add x to every element).

then we set out[] = [1,4,4,5,0](out[i]=in[i]);

we scan the out[] from the end, and find the first none-zero element, store it index as p, and p means, we will parse out[p].

Count how much element appears and we will get the result.

[1,4,4,5,0] , p = 3, cnt = 1 (parse out[3] = 5)
->
[1,4,4,5,1] , p = 2, cnt = 3 (parse 4)
->
[1,3,3,3,1] , p = 0, cnt = 3 (parse 1)     
->
[4,3,3,3,1] , p = -1, cnt = 4 (done)     

when we parse out[i](that is in[i]), we will assign next_parse_element ~last_element_assigned-1, by our assumption, it's next_element_index + 1~last element assigned-1, but next_element_index + 1~last element assigned is be parsed by our program and useless.

Example([1,4,4,5]): when we parse 4, the next element is 1, so we should calculate out[1](next parse element) ~ out[3](last_assigned - 1). But you see, out[1] - out[3] is useless, and we don't lose any information.

if not match the assumption, we can add x to every element(in[i]+=x) to match the assumption (at most add size of in, still O(n) space). Then we do it as above method, and ignore the x elements in the beginning of out[], and it's the real answer for the input.

add 1 to every element in int[]
4 | x x
3 | x x x x x
2 | x x x x x
1 | x x x x x x
    - - - - - -
    1 2 3 4 5 6

It's [4,4,3,3,3,1], ignore the first element and it's the real answer.

Time Complexity. If in[] is not sorted, then it is O(nlogn), or it's O(n).

See my code for detail:

import java.util.Arrays;


public class Conjugate {
    int[] part;
    public Conjugate(int[] array) {
        Arrays.sort(array);
        int max = 0;
        for (int i = 0; i < array.length; i++)
        {
            max = Math.max(max, array[i]);
        }
        part = new int[Math.max(max,array.length)];
        for (int i = 0;i < array.length; i++)
        {
            part[i] = array[i];
        }
        int cnt = 0, p = part.length - 1, next = 0;
        for (int i = array.length-1; i >= 0; i--)
        {
            for (int j = i; j>=0&&part[i]==part[j]; j--)
            {
                cnt ++;
                if (j - 1 < 0)
                    next = 0;
                else 
                    next = part[j-1];
                i=j;
            }
            for (int j = p; j >= next ; j--)
            {
                part[j] = cnt;
            }
            p = next - 1 ;
        }
    }
    void output()
    {
        for (int i = 0; i < part.length; i++)
        {
            System.out.print(part[i] + " ");
        }
    }
    public static void main(String[] args) {
        int[] a = {1,4,4,5};
        Conjugate con = new Conjugate(a);
        con.output();
    }
}

Answer 3

This answer describes an algorithm that arguably is not in-place on account of its using the sign bit. Since you're using a signed type, I'm going to post it anyway.

Each partition is defined uniquely by its maxima. For your example partition

4 | x
3 | x x x x
2 | x x x x
1 | x x x x x
    - - - - -
    1 2 3 4 5

where I have labeled the axes by coordinates instead of by the internal representation of the partition and its transpose, the maxima are (1, 4), (4, 3), and (5, 1).

The first/last step of the algorithm is to convert to and from a representation that describes the maxima. In general, we have room only for one coordinate, so we have to use position in the vector to describe the other. The forward transformation is just replacing all but the last occurrence of each number by 0.

5 4 4 1   -> 5 0 4 1
4 3 3 3 1 -> 4 0 0 3 1
             - - - - -
             1 2 3 4 5

Both the forward and backward transformations are easy to implement.

The middle step is to do the transpose on this alternative representation. Scan through the array, looking for positive integers. When we find one, say x at position y, write a 0 to position y and write -y to position x. Actually life is a bit more complicated than that; if position x contains a positive integer, then we need to store it in a temporary and then handle it next. Finally, scan through the array replacing -x by x (obviously this doesn't need to be a separate step). In summary, we are effecting a permutation and have available a bit to remember whether a particular item has moved.