如何索引双重限制的整数分区？
How to index doubly restricted integer partitions?
枚举一个正整数的所有分区时，有以下2个限制：
- 每个分区的大小总是
PartitionSize
- 这些分区的所有元素都小于或等于
MaxVal，并且大于零。
...我面临 numbering/indexing 这些分区的任务，以这种方式我可以存储它们的索引并稍后检索它们以从任意索引快速重新生成一个分区的元素。索引不需要连续。
问：计算此类分区索引的最佳方法是什么？
生成这些分区的函数如下：
void GenPartitions(const unsigned int myInt, const unsigned int PartitionSize, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, PartitionSize, MaxVal)) == 0)
return;
unsigned int MinVal = 1;
unsigned int idx_Last = PartitionSize - 1;
unsigned int RightSum = MaxVal; //Sum to the right of the Decrement Point (inclusive)
unsigned int idx_Dec = idx_Last; //The point that needs to be decremented
vector<unsigned int> partition(PartitionSize);
partition[idx_Last] = MaxVal; //Initiallize first partition
do {
unsigned int cur = idx_Dec - 1;
unsigned int LeftRemain = myInt - RightSum - (idx_Dec - 1) * MinVal; //Calculate the remainder to the left
while (LeftRemain > partition[idx_Dec]) //While the remainder is too big to satisfy the left to right ascending ordering.
{
LeftRemain -= partition[idx_Dec] - 1; //
partition[cur--] = partition[idx_Dec];
}
partition[cur] = LeftRemain; //Last remainder
for (unsigned int i = 0; i < cur; i++) //Set the elements where the reminder did not reach.
partition[i] = MinVal;
for (auto d : partition) //DISPLAY THE PARTITON HERE ...or do sth else with it.
std::cout << setw(2) << d << ",";
std::cout << endl;
for (idx_Dec = 0; (idx_Dec < idx_Last) && (partition[idx_Dec] + 1 > partition[idx_Dec + 1]); idx_Dec++); //Find the rising edge
unsigned int val_1stUp = partition[idx_Dec]+1;
for (++idx_Dec; (idx_Dec <= idx_Last) && (val_1stUp > partition[idx_Dec] - 1); idx_Dec++); //Find the falling edge occuring AFTER the rising edge.
if (idx_Dec > idx_Last)
break; //Could not find the falling edge. We are done.
partition[idx_Dec]--; //Decrement at the Decrement Point
//std::cout << setw((idx_Dec*3)+1) << "" << "v" << endl; //Show the Decrement Points
RightSum = 0; //This needs optimization. There is no need to start from the Decrement Point every time. This sum can be adjusted on-the-go, as changes are made to the partition.
for (unsigned int i = idx_Dec; i <= idx_Last; i++) //Calculate the sum to the right of the Decrement Point (inclusive). This needs optimization.
RightSum += partition[i];
} while(true);
}
请注意，此函数会生成分区，其中每个分区中的所有元素都按从小到大（从左到右）的顺序排列。此功能不能损坏。
分区本身（垂直）之间的排序是字典顺序的。失去它我会不高兴，但我可以没有它。
SAMPLE OUTPUT OF: GenPartitions(20, 4, 10):
1, 1, 8,10
1, 2, 7,10
1, 3, 6,10
2, 2, 6,10
1, 4, 5,10
2, 3, 5,10
2, 4, 4,10
3, 3, 4,10
1, 1, 9, 9
1, 2, 8, 9
1, 3, 7, 9
2, 2, 7, 9
1, 4, 6, 9
2, 3, 6, 9
1, 5, 5, 9
2, 4, 5, 9
3, 3, 5, 9
3, 4, 4, 9
1, 3, 8, 8
2, 2, 8, 8
1, 4, 7, 8
2, 3, 7, 8
1, 5, 6, 8
2, 4, 6, 8
3, 3, 6, 8
2, 5, 5, 8
3, 4, 5, 8
4, 4, 4, 8
1, 5, 7, 7
2, 4, 7, 7
3, 3, 7, 7
1, 6, 6, 7
2, 5, 6, 7
3, 4, 6, 7
3, 5, 5, 7
4, 4, 5, 7
2, 6, 6, 6
3, 5, 6, 6
4, 4, 6, 6
4, 5, 5, 6
5, 5, 5, 5
此外，我特意选择不要将其实现为递归函数，因为性能低下并且RAM/stack递归解决方案对非常大的分区有影响（尽管他们更简单的实现）。
如果有人想编译它，下面是辅助函数。
#include <iostream>
#include <iomanip>
#include <vector>
unsigned int MaxPartitionVal(const unsigned int myInt, const unsigned int PartitionSize, unsigned int MaxVal)
{
if ((myInt < 2) || (PartitionSize < 2) || (MaxVal < 1) || (PartitionSize > myInt) || (myInt > (PartitionSize*MaxVal))) //Sanity checks
return 0;
unsigned int last = PartitionSize - 1;
if (MaxVal + last > myInt)
MaxVal = myInt - last; //It is not always possible to start with the MaxValue. Decrease it to sth possible
return MaxVal;
}
提供此答案是希望它有用，但不保证最佳:)。
符号
首先，一些 typedef（根据需要更改）：
using iType = uint_fast64_t; // Type of the generated indices.
using pType = unsigned; // Type of the parts in a partition.
using pSize = std::vector<pType>::size_type; // Size of a partition.
符号：
parts(num, size, max) 是 num 的整数分区集，有 size 个部分低于或等于 max.p 是 parts 的一个元素（一个 std::vector，所以索引为 0）。getIndex(p, num, size, max) 计算 p 的索引。getPartition(index, num, size, max) 计算给定 index.
基本思路
由于索引不必是连续的，我们可以这样重新表述问题：
getIndex(...) 将多个整数复用（或压缩）为一个整数。getPartition(...) 将单个整数多路分解（或解压缩）为原始整数。
一个常见的解决方案是：
- 使用连续的加法和乘法进行多路复用。
- 使用连续的欧几里德除法和模数解复用。
因为我们知道分区的每个 part 验证 1 <= part && part <= max，第一个实现可以是：
iType getIndex(const std::vector<pType>& partition, pType max) {
pSize i = partition.size();
iType result = 0;
while (i > 0) {
i--;
const pType iMin = 1;
const pType iMax = max;
pType part = partition[i];
result = result*(iMax+1-iMin) + (part-iMin);
}
return result;
}
std::vector<pType> getPartition(iType index, pSize size, pType max) {
std::vector<pType> result(size,0);
iType currentIndex = index;
for (pSize i = 0; i < size; i++) {
const pType iMin = 1;
const pType iMax = max;
pType divider = iMax + 1 - iMin;
result[i] = iMin + currentIndex % divider;
currentIndex = currentIndex / divider;
}
return result;
}
这行得通，但是计算出的索引非常大。获得较低索引的技巧是在每个循环迭代中计算 iMax 和 iMin 的更精细值，利用我们正在处理分区而不是 [1;max] 中的库向量这一事实.
具有范围限制的更好压缩
添加 self-imposed 约束：
- 分区从大到小排序：
p[i] >= p[i+1]
我们可以推断，对于 parts(num, size, max) 中的 p：
p[0] >= 1 + (num-1) / sizep[0] <= num + 1 - size
约束 2 和 3 可以递归地应用于所有 p[i]，注意 p[1..size-1] 在 parts(num-p[0], size-1, p[0])
中
因此我们可以更好地计算iMin & iMax，并将它们注入到之前的实现中：
// !! Requires a sorted partition, from greatest to lowest part.
iType getIndex2(const std::vector<pType>& partition, pType max) {
pSize size = partition.size();
iType result = 0;
pType currentNum = 0;
pSize i = partition.size();
while (i > 0) {
i--;
pType part = partition[i];
currentNum = currentNum + part;
pType iMax = currentNum+1-(size-i); // constraint 3
if (i > 0) {
iMax = std::min<pType>(iMax, partition[i-1]); // constraint 1
} else {
iMax = std::min<pType>(iMax, max);
}
pType iMin = 1+(currentNum-1)/(size-i); // constraint 2
result = result*(iMax+1-iMin) + (part-iMin);
}
return result;
}
std::vector<pType> getPartition2(iType index, pType num, pSize size, pType max) {
std::vector<pType> result(size,0);
iType currentIndex = index;
pType iMax = std::min<pType>(max, num + 1 - size); // constraint 3
pType currentNum = num;
for (pSize i = 0; i < size; i++) {
pType iMin = 1+(currentNum-1)/(size-i); // constraint 2
pType diviser = iMax+1-iMin;
result[i] = iMin + currentIndex % diviser;
currentIndex = currentIndex / diviser;
currentNum = currentNum - result[i];
iMax = std::min<pType>(result[i], currentNum + 1 - (size - i -1)); // constraint 1 & 3 for step (i+1)
}
return result;
}
待办事项
- 完整性检查：如果分区未排序或 partition/index 无效，则提供的实现可能会出现未定义的行为。
- 评估何时
iType 会溢出（并检查它是否适合您）。我不知道索引的增长速度取决于 num、size 和 max.
枚举一个正整数的所有分区时，有以下2个限制：
- 每个分区的大小总是
PartitionSize - 这些分区的所有元素都小于或等于
MaxVal，并且大于零。
...我面临 numbering/indexing 这些分区的任务，以这种方式我可以存储它们的索引并稍后检索它们以从任意索引快速重新生成一个分区的元素。索引不需要连续。
问：计算此类分区索引的最佳方法是什么？
生成这些分区的函数如下：
void GenPartitions(const unsigned int myInt, const unsigned int PartitionSize, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, PartitionSize, MaxVal)) == 0)
return;
unsigned int MinVal = 1;
unsigned int idx_Last = PartitionSize - 1;
unsigned int RightSum = MaxVal; //Sum to the right of the Decrement Point (inclusive)
unsigned int idx_Dec = idx_Last; //The point that needs to be decremented
vector<unsigned int> partition(PartitionSize);
partition[idx_Last] = MaxVal; //Initiallize first partition
do {
unsigned int cur = idx_Dec - 1;
unsigned int LeftRemain = myInt - RightSum - (idx_Dec - 1) * MinVal; //Calculate the remainder to the left
while (LeftRemain > partition[idx_Dec]) //While the remainder is too big to satisfy the left to right ascending ordering.
{
LeftRemain -= partition[idx_Dec] - 1; //
partition[cur--] = partition[idx_Dec];
}
partition[cur] = LeftRemain; //Last remainder
for (unsigned int i = 0; i < cur; i++) //Set the elements where the reminder did not reach.
partition[i] = MinVal;
for (auto d : partition) //DISPLAY THE PARTITON HERE ...or do sth else with it.
std::cout << setw(2) << d << ",";
std::cout << endl;
for (idx_Dec = 0; (idx_Dec < idx_Last) && (partition[idx_Dec] + 1 > partition[idx_Dec + 1]); idx_Dec++); //Find the rising edge
unsigned int val_1stUp = partition[idx_Dec]+1;
for (++idx_Dec; (idx_Dec <= idx_Last) && (val_1stUp > partition[idx_Dec] - 1); idx_Dec++); //Find the falling edge occuring AFTER the rising edge.
if (idx_Dec > idx_Last)
break; //Could not find the falling edge. We are done.
partition[idx_Dec]--; //Decrement at the Decrement Point
//std::cout << setw((idx_Dec*3)+1) << "" << "v" << endl; //Show the Decrement Points
RightSum = 0; //This needs optimization. There is no need to start from the Decrement Point every time. This sum can be adjusted on-the-go, as changes are made to the partition.
for (unsigned int i = idx_Dec; i <= idx_Last; i++) //Calculate the sum to the right of the Decrement Point (inclusive). This needs optimization.
RightSum += partition[i];
} while(true);
}
请注意，此函数会生成分区，其中每个分区中的所有元素都按从小到大（从左到右）的顺序排列。此功能不能损坏。
分区本身（垂直）之间的排序是字典顺序的。失去它我会不高兴，但我可以没有它。
SAMPLE OUTPUT OF: GenPartitions(20, 4, 10):
1, 1, 8,10
1, 2, 7,10
1, 3, 6,10
2, 2, 6,10
1, 4, 5,10
2, 3, 5,10
2, 4, 4,10
3, 3, 4,10
1, 1, 9, 9
1, 2, 8, 9
1, 3, 7, 9
2, 2, 7, 9
1, 4, 6, 9
2, 3, 6, 9
1, 5, 5, 9
2, 4, 5, 9
3, 3, 5, 9
3, 4, 4, 9
1, 3, 8, 8
2, 2, 8, 8
1, 4, 7, 8
2, 3, 7, 8
1, 5, 6, 8
2, 4, 6, 8
3, 3, 6, 8
2, 5, 5, 8
3, 4, 5, 8
4, 4, 4, 8
1, 5, 7, 7
2, 4, 7, 7
3, 3, 7, 7
1, 6, 6, 7
2, 5, 6, 7
3, 4, 6, 7
3, 5, 5, 7
4, 4, 5, 7
2, 6, 6, 6
3, 5, 6, 6
4, 4, 6, 6
4, 5, 5, 6
5, 5, 5, 5
此外，我特意选择不要将其实现为递归函数，因为性能低下并且RAM/stack递归解决方案对非常大的分区有影响（尽管他们更简单的实现）。
如果有人想编译它，下面是辅助函数。
#include <iostream>
#include <iomanip>
#include <vector>
unsigned int MaxPartitionVal(const unsigned int myInt, const unsigned int PartitionSize, unsigned int MaxVal)
{
if ((myInt < 2) || (PartitionSize < 2) || (MaxVal < 1) || (PartitionSize > myInt) || (myInt > (PartitionSize*MaxVal))) //Sanity checks
return 0;
unsigned int last = PartitionSize - 1;
if (MaxVal + last > myInt)
MaxVal = myInt - last; //It is not always possible to start with the MaxValue. Decrease it to sth possible
return MaxVal;
}
提供此答案是希望它有用，但不保证最佳:)。
符号
首先，一些 typedef（根据需要更改）：
using iType = uint_fast64_t; // Type of the generated indices.
using pType = unsigned; // Type of the parts in a partition.
using pSize = std::vector<pType>::size_type; // Size of a partition.
符号：
parts(num, size, max)是num的整数分区集，有size个部分低于或等于max.p是parts的一个元素（一个std::vector，所以索引为 0）。getIndex(p, num, size, max)计算p的索引。getPartition(index, num, size, max)计算给定index. 的分区
基本思路
由于索引不必是连续的，我们可以这样重新表述问题：
getIndex(...)将多个整数复用（或压缩）为一个整数。getPartition(...)将单个整数多路分解（或解压缩）为原始整数。
一个常见的解决方案是：
- 使用连续的加法和乘法进行多路复用。
- 使用连续的欧几里德除法和模数解复用。
因为我们知道分区的每个 part 验证 1 <= part && part <= max，第一个实现可以是：
iType getIndex(const std::vector<pType>& partition, pType max) {
pSize i = partition.size();
iType result = 0;
while (i > 0) {
i--;
const pType iMin = 1;
const pType iMax = max;
pType part = partition[i];
result = result*(iMax+1-iMin) + (part-iMin);
}
return result;
}
std::vector<pType> getPartition(iType index, pSize size, pType max) {
std::vector<pType> result(size,0);
iType currentIndex = index;
for (pSize i = 0; i < size; i++) {
const pType iMin = 1;
const pType iMax = max;
pType divider = iMax + 1 - iMin;
result[i] = iMin + currentIndex % divider;
currentIndex = currentIndex / divider;
}
return result;
}
这行得通，但是计算出的索引非常大。获得较低索引的技巧是在每个循环迭代中计算 iMax 和 iMin 的更精细值，利用我们正在处理分区而不是 [1;max] 中的库向量这一事实.
具有范围限制的更好压缩
添加 self-imposed 约束：
- 分区从大到小排序：
p[i] >= p[i+1]
我们可以推断，对于 parts(num, size, max) 中的 p：
p[0] >= 1 + (num-1) / sizep[0] <= num + 1 - size
约束 2 和 3 可以递归地应用于所有 p[i]，注意 p[1..size-1] 在 parts(num-p[0], size-1, p[0])
因此我们可以更好地计算iMin & iMax，并将它们注入到之前的实现中：
// !! Requires a sorted partition, from greatest to lowest part.
iType getIndex2(const std::vector<pType>& partition, pType max) {
pSize size = partition.size();
iType result = 0;
pType currentNum = 0;
pSize i = partition.size();
while (i > 0) {
i--;
pType part = partition[i];
currentNum = currentNum + part;
pType iMax = currentNum+1-(size-i); // constraint 3
if (i > 0) {
iMax = std::min<pType>(iMax, partition[i-1]); // constraint 1
} else {
iMax = std::min<pType>(iMax, max);
}
pType iMin = 1+(currentNum-1)/(size-i); // constraint 2
result = result*(iMax+1-iMin) + (part-iMin);
}
return result;
}
std::vector<pType> getPartition2(iType index, pType num, pSize size, pType max) {
std::vector<pType> result(size,0);
iType currentIndex = index;
pType iMax = std::min<pType>(max, num + 1 - size); // constraint 3
pType currentNum = num;
for (pSize i = 0; i < size; i++) {
pType iMin = 1+(currentNum-1)/(size-i); // constraint 2
pType diviser = iMax+1-iMin;
result[i] = iMin + currentIndex % diviser;
currentIndex = currentIndex / diviser;
currentNum = currentNum - result[i];
iMax = std::min<pType>(result[i], currentNum + 1 - (size - i -1)); // constraint 1 & 3 for step (i+1)
}
return result;
}
待办事项
- 完整性检查：如果分区未排序或 partition/index 无效，则提供的实现可能会出现未定义的行为。
- 评估何时
iType会溢出（并检查它是否适合您）。我不知道索引的增长速度取决于num、size和max.