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

score 1 · Accepted Answer

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

符号

首先，一些 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(a的一个元素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] 中的任意向量这一事实。

具有范围限制的更好压缩

添加一个自我施加的约束：

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

我们可以推断，对于pin parts(num, size, max)：

p[0] >= 1 + (num-1) / size
p[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;
}

现场演示

去做

健全性检查：如果分区未排序或分区/索引无效，则提供的实现可能会进入未定义的行为。
评估何时iType会溢出（并检查它是否适合您）。我不知道指数的增长速度取决于num和。sizemax

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

1 回答 1

符号

基本理念

具有范围限制的更好压缩

去做

Related

Reference