When enumerating all partitions of a positive integer with the following 2 restrictions:
PartitionSize MaxVal, and greater than zero....I am faced with a task of numbering/indexing these partitions, in such manner that I can store their indices and later retrieve them to quickly regenerate the elements of one partition from an arbitrary index. The indices do not need to be consecutive.
Q: What would be the best way to go about calculating such partition indices?
The function that generates these partitions is listed below:
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);
}
Note, that this functions generates partitions in which all elements in each partition are ordered from smallest to largest (left to right). This feature cannot become broken.
The ordering between partitions themselves (vertical) is lexicographic. I would not be happy to lose it, but I could live without it.
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
Also, I purposely elected not to implement this as a recursive function, because of low performance and RAM/stack impact that recursive solutions have for very large partitions (despite their simpler implementations).
Below are the helper functions if anyone wants to compile it.
#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;
}
This answer is provided in the hope that it is useful, but without any warranty of being optimal :).
First, a few typedefs (change as needed):
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.
Notations:
parts(num, size, max) is the set of integer partitions of num, having size parts inferior or equal to max.p is an element of parts (a std::vector, so 0 indexed).getIndex(p, num, size, max) computes the index of p.getPartition(index, num, size, max) computes the partition of the given index.Since indices don't have to be consecutive, we can rephrase the problem as such:
getIndex(...) multiplexes (or compresses) multiple integers into a single one.getPartition(...) demultiplexes (or decompresses) the single integer into the original ones.A common solution to that is:
Since we know that each part of a partition verifies 1 <= part && part <= max, a first implementation can be:
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;
}
This works, however computed indices are quite large. The trick to get lower indices is to compute finer values of iMax and iMin at each loop iteration, using the fact that we're working on partitions, not on an aribrary vector in [1;max].
Adding a self-imposed constraint:
p[i] >= p[i+1]We can deduce, for p in parts(num, size, max):
p[0] >= 1 + (num-1) / sizep[0] <= num + 1 - sizeConstraints 2 & 3 can be applied recursively to all p[i], by noting that p[1..size-1] is in parts(num-p[0], size-1, p[0])
Therefore we can compute better iMin & iMax, and inject them in the previous implementation:
// !! 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;
}
iType will be overflowed (and check if it's good enough for you). I don't know how fast the indices grows depending on num,size and max.