1

When enumerating all partitions of a positive integer with the following 2 restrictions:

  • the size of each partition is always PartitionSize
  • all elements of these partitions are less than or equal to 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;
}
George Robinson
  • 1,500
  • 9
  • 21
  • Do you have evidence about the performance (or memory usage) of recursive approaches here? – Davis Herring Jun 22 '19 at 21:55
  • is your partition like: https://en.wikipedia.org/wiki/Partition_(number_theory) ? – Ray Tayek Jun 22 '19 at 22:38
  • [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/9716597) – L. F. Jun 23 '19 at 01:02
  • @Davis. Yes. Process Explorer shows ridiculous Private Bytes for recursive versions with large partitions...and stack overflows if I don't increase it. – George Robinson Jun 23 '19 at 11:25
  • @GeorgeRobinson: That much stack usage is its own (additional) bug; you should “run out” of time before you run out of space for even a weakly exponential function. – Davis Herring Jun 23 '19 at 14:17
  • @Ray: Yes, except that its size and magnitude of elements are restricted...and it does not contain zeros. – George Robinson Jun 23 '19 at 17:30
  • 1
    Do you need consecutives indices (if there are N solutions,indices need to be between 1 and N) ? If not, do you have a constraint on indices (ex: max value depending on N) ? – Vincent Saulue-Laborde Jun 24 '19 at 17:51
  • 1
    related: https://stackoverflow.com/questions/30893292/generate-all-partitions-of-a-set https://math.stackexchange.com/questions/222780/enumeration-of-set-partitions maybe you could generate all of the subets and throw away what you do not want: https://academic.oup.com/comjnl/article/32/3/281/331557 – Ray Tayek Jun 24 '19 at 21:56
  • 1
    @Vincent: No, I do not need consecutive indices. Just unique ones...and easily reversible. – George Robinson Jun 24 '19 at 22:45
  • @Ray: Thanks for the link, but I gut stuck calculating how many of these partitions exist in the first place. This is needed for that algorithm. Apparently, this problem has been solved for singly restricted partitions, but not for doubly restricted ones. See: https://math.stackexchange.com/questions/3269228/integer-partitions-with-double-restriction – George Robinson Jun 24 '19 at 22:51
  • 1
    @GeorgeRobinson: Maybe this link can be helpful: http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/partition.html. It depends of course how intelligent the implementation is. – Aleph0 Jun 27 '19 at 10:45

1 Answers1

1

This answer is provided in the hope that it is useful, but without any warranty of being optimal :).

Notations

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.

Basic idea

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:

  • multiplexing using consecutives additions & multiplications.
  • demultiplexing using consecutives euclidian divisions & modulos.

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;
}

Live demo

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].

Better compression with range constraints

Adding a self-imposed constraint:

  1. partitions are sorted from largest to lowest part: p[i] >= p[i+1]

We can deduce, for p in parts(num, size, max):

  1. p[0] >= 1 + (num-1) / size
  2. p[0] <= num + 1 - size

Constraints 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;
}

Live demo

TODO

  • sanity checks: the provided implementations can go into undefined behaviour if the partition is not sorted, or the partition/index is not valid.
  • evaluate when 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.
Vincent Saulue-Laborde
  • 1,167
  • 8
  • 12