c – 共轭整数分区到位

概述我正在构建一个包含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 我正在构建一个包含Partitions类的C库.我试图实现共轭(下面解释)到位,我不能让它工作.

我的班级成员是：

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 switchedn_i = sum{ m_j | m_j > i}

例如,[5,1]的缀合物是[4,3,1].另一种看法是将分区绘制为单位正方形行,其中第i行的平方数为m_i.读取列的高度然后给出共轭.对于同一个例子,图片是

1| x4| x x x x4| x x x x5| x x x x x  __________   4 3 3 3 1

数学转换为编程语法为m_i = _parts [i-1]和k = _length.这是一个破坏的共轭实现：

voIDPartition::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...1x m_k   x(m_(k-1)-m_k)      x(m_1 - m_2)

使用这个想法,我有以下实现,给出正确的答案：

voIDPartition::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的回答(下面接受),这里是最终的代码(详见他的答案)：

voIDPartition::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个线程中完成：

>确定允许执行共轭而不重叠的最小向量大小.
>反向原分区;由于相对于输入的输出反转允许较少的重叠,因此减少额外的空间.
>通过用适当的索引填充向量执行共轭,重复与原始分区中的相邻值之间的差异多次.

这里是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个这样的零).

总结

以上是内存溢出为你收集整理的c – 共轭整数分区到位全部内容，希望文章能够帮你解决c – 共轭整数分区到位所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。