我正在构建一个包含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;
}
与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;
}
这可以在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})，只向vector中添加一个额外的元素。在较复杂的情况下(如{4,4,4,4})，vector的大小临时加倍。
可以在不使用太多额外空间的情况下使用这种方法。因为像{4,4,4,4}这样的"坏"情况显然具有非常低的熵，我们可以压缩原始分区。但是这会使代码复杂化。
RLE和增量编码的结合使该算法真正到位(这意味着O(1)额外的空间)。使用正数(或零高位)来编码原始分区中相邻值之间的差异(因为共轭步骤无论如何只需要差异)。使用负数(或非零高位位)对零进行编码(数字的剩余位表示有多少个零)。所有这些限制了delta值和零计数器的一半范围。但在这两种情况下，最多可能有一个值超过了范围的一半。所以我们可以在这个超大的值前面加上一个0(并且在向量中保留最多2个这样的0的空间)。
这个答案描述了一种算法，由于它使用了符号位，因此可以说是不合适的。既然你用的是带符号的类型，我还是把它贴出来吧。
每个分区由其最大值唯一地定义。对于您的示例分区
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
向前和向后转换都很容易实现。
中间步骤是对这个替代表示法进行转置。扫描数组，寻找正整数。当我们找到一个时，说x在位置y，写一个0到位置y，写一个-y到位置x。实际上，生活比这要复杂一些;如果位置x包含一个正整数，那么我们需要将它存储在一个临时对象中，然后再处理它。最后，扫描用x替换-x的数组(显然这不需要单独的步骤)。总之，我们正在执行一个排列，并且有可用的位来记住特定的项是否移动。
输入数组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-1，根据我们的假设，它是next_element_index + 1~last element assigned-1，但next_element_index + 1~last element assigned被我们的程序解析并且无用。
示例([1,4,4,5]):解析4时，下一个元素是1，因此要计算out[1](next parse element) ~ out[3](last_assigned - 1)。但是你看，out[1] - out[3]是无用的，我们不会丢失任何信息。
如果不匹配假设，我们可以在每个元素(in[i]+=x)上添加x来匹配假设(最多添加in的大小，仍然是O(n)的空间)。然后我们按照上面的方法来做，忽略out[]开头的x元素，这就是输入的真实答案。
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();
}
}