我的班级成员是：
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;
}
解决方法
>确定允许执行共轭而不重叠的最小向量大小.
>反向原分区;由于相对于输入的输出反转允许较少的重叠,因此减少额外的空间.
>通过用适当的索引填充向量执行共轭,重复与原始分区中的相邻值之间的差异多次.
这里是C11实现(另见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);
}
这种实现在某种意义上就位.意思是它使用单个向量并最小化共轭所需的额外空间.在某些情况下(如{4,1,1}或{4,2,1}),向量中只添加一个额外的元素.在困难的情况下(如{4,4})的矢量大小暂时加倍.
可以使用这种方法,而不用太多的空间.由于{4,4}的“不良”情况显然具有非常低的熵,我们可以压缩原始分区.但是这会使代码复杂化.
RLE和delta编码的组合使得该算法真正在原位(这意味着O(1)额外的空间).使用正数(或零高位)来对原始分区中相邻值之间的差异进行编码(因为共轭步骤仅需要差异).使用负数(或非零高位)来编码零的运行(数字的剩余位告诉多少个零).所有这些限制了增量值和零计数器到一半的范围.但在这两种情况下,最多可能有一个值超过范围的一半.所以我们可以把这个超大的值加上一个零(并且向量中的保留空间最多为2个这样的零).
