10

我正在构建一个包含 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第 th 行中的正方形数量为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;
}

但是，它使用另一个标准向量，我试图避免。

根据 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;
}
4

3 回答 3

2

这可以在 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 个这样的零保留空间）。

于 2014-07-24T11:45:32.143 回答
1

输入数组in[] = [1,4,4,5]，假设in[i]>=i+1（如果不是，则将 x 添加到每个元素）。

然后我们设置out[] = [1,4,4,5,0]( out[i]=in[i]);

我们从头开始扫描out[]，找到第一个非零元素，将它的索引存储为p，这p意味着我们将解析out[p]。

计算出现了多少元素，我们将得到结果。

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

当我们解析out[i]（即）时，根据我们的假设，in[i]我们将分配它，但是被我们的程序解析并且无用。next_parse_element ~last_element_assigned-1next_element_index + 1~last element assigned-1next_element_index + 1~last element assigned

Example([1,4,4,5])：当我们解析 时4，下一个元素是1，所以我们应该计算out[1](next parse element) ~ out[3](last_assigned - 1)。但是你看，out[1] - out[3]是没用的，而且我们不会丢失任何信息。

如果不匹配假设，我们可以将 x 添加到每个元素（in[i]+=x）以匹配假设（最多添加大小in，静止O(n)空间）。然后我们按照上面的方法做，忽略x开头的元素，out[]这是输入的真正答案。

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

它是[4,4,3,3,3,1]，忽略第一个元素，这是真正的答案。

时间复杂度。如果in[]未排序，则为O(nlogn)，或为O(n)。

有关详细信息，请参阅我的代码：

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();
    }
}
于 2014-07-24T04:51:50.857 回答
1

这个答案描述了一种算法，由于它使用符号位，可以说它是不合适的。由于您使用的是签名类型，因此无论如何我都会发布它。

每个分区由其最大值唯一定义。对于您的示例分区

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

我用坐标而不是分区的内部表示及其转置来标记轴，最大值是 (1, 4)、(4, 3) 和 (5, 1)。

算法的第一步/最后一步是与描述最大值的表示进行转换。一般来说，我们只有一个坐标的空间，所以我们必须使用向量中的位置来描述另一个。前向变换只是将每个数字的最后一次出现之外的所有数字都替换为 0。

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

前向和后向转换都很容易实现。

中间步骤是对这个替代表示进行转置。扫描数组，寻找正整数。当我们找到一个时，说xat position y，写 a 0to positiony和 write -yto position x。其实生活比这复杂一点；如果位置x包含一个正整数，那么我们需要将它存储在一个临时的，然后再处理它。最后，扫描替换为的数组-x（x显然这不需要是一个单独的步骤）。总而言之，我们正在实现一个排列，并且可以记住某个特定项目是否已移动。

于 2014-07-24T03:55:10.187 回答