c++ - 如何索引双重限制的整数分区？

Question

枚举正整数的所有分区时，有以下2个限制:

• 每个分区的大小总是PartitionSize
• 这些分区的所有元素都小于或等于 MaxVal，并且大于零。

...我面临着对这些分区进行编号/索引的任务，以这种方式我可以存储它们的索引并稍后检索它们以从任意索引快速重新生成一个分区的元素。索引不需要连续。

问:计算此类分区索引的最佳方法是什么？

生成这些分区的函数如下所示:

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/堆栈影响(尽管它们的实现更简单)。

如果有人想编译它，下面是辅助函数。

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

Answer 1

提供此答案是希望它有用，但不保证最佳:)。

符号

首先，一些 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;
}

Live demo

这可行，但是计算的索引非常大。获得较低索引的技巧是计算更精细的值 iMax和 iMin在每个循环迭代中，使用我们正在处理分区而不是 [1;max] 中的库 vector 这一事实。

具有范围限制的更好压缩

添加一个 self 强加的约束:

1. 分区从大到小排序:p[i] >= p[i+1]

我们可以推断，对于p在parts(num, size, max) :

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

约束 2 和 3 可以递归地应用于所有 p[i] , 通过注意到 p[1..size-1]在parts(num-p[0], size-1, p[0])

因此我们可以更好地计算iMin & iMax ，并在之前的实现中注入(inject)它们:

// !! 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

待办事项

• 完整性检查:如果分区未排序或分区/索引无效，则提供的实现可能会出现未定义的行为。
• 评估何时 iType会溢出(并检查它是否对你来说足够好)。我不知道指数增长的速度取决于 num , size和 max .