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。
活用を考えるもう 1 つの方法は、活用が次のシーケンスであることを認識することです。
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;
}