将整数范围划分为几乎相等的整数范围

Question

我正在编写一个算法，涉及将一组数字放入桶中。你能帮忙实现这两种简单方法吗？如果需要更多解释，请告诉我。

// return a vector where each element represents the
// size of the range of numbers in the corresponding bucket
// buckets should be equal in size +/- 1
// doesn't matter where the bigger/smaller buckets are
vector<int> makeBuckets(int max, int numberOfBuckets);

// return which bucket n belongs in
int whichBucket(int max, int numberOfBuckets, int n); 

示例输出

makeBuckets(10, 3) == { 3, 3, 4 }; // bucket ranges: (0, 2), (3, 5), (6, 9)
whichBucket(10, 3, 0) == 0;
whichBucket(10, 3, 1) == 0;
whichBucket(10, 3, 2) == 0;
whichBucket(10, 3, 3) == 1;
whichBucket(10, 3, 4) == 1;
whichBucket(10, 3, 5) == 1;
whichBucket(10, 3, 6) == 2;
whichBucket(10, 3, 7) == 2;
whichBucket(10, 3, 8) == 2;
whichBucket(10, 3, 9) == 2;

- cambunctious

---

在“parts”的声明中，“size”的含义是什么？它是桶的数量还是每个桶的大致大小？此外，您的算法应如何将10分成4个桶 - “2, 2, 2, 4”可接受吗？“3, 3, 3, 1”可接受吗？是否只有一个正确答案，或者在选择如何拆分项目方面有任何自由度？我认为您必须回答所有这些问题才能使您的帖子更清晰。 - anatolyg

谢谢@anatolyg。我编辑了我的问题。 - cambunctious

Answer 1

假设您需要将范围[0，n]分成k个桶。

1. e = n / k（整数除法！）将告诉您每个桶的最小大小。 2. o = n％k将告诉您有多少个桶需要增加大小。 3. 现在循环k：

- 如果o> 0，则创建一个大小为e + 1的桶，减少o。 - 如果o == 0，则创建一个大小为e的桶。

如何最好地创建桶取决于n的大小。例如，如果n很小，您可以只有一个大小为n的数组，其中存储每个数字的桶索引。在上面的循环中，您将填充该数组。然后查询whichBucket（）将以O（1）运行。

但是，如果n很大，则这是不切实际的。在这种情况下，您将完全隐式地进行桶排序。这意味着对于每个传入的查询，您都可以直接使用e和o计算相应的桶索引。

- ypnos

Answer 2

感谢ypnos的回答。这是我在C++中的实现。

vector<int> makeBuckets(int max, int numberOfBuckets) {
    int e = max / numberOfBuckets;
    vector<int> b(numberOfBuckets, e);
    fill(b.begin(), b.begin() + (max % numberOfBuckets), e + 1);
    return b;
}

int whichBucket(int max, int numberOfBuckets, int n) {
    return n * numberOfBuckets / max;
}

- cambunctious

---

返回 n * numberOfBuckets / max; 不需要浮点数。 - Ivan Baldin

@IvanBaldin 谢谢，我已经修改了。我担心会发生溢出问题，但在大多数情况下这可能不是问题。 - cambunctious

Answer 3

您可以使用简单的实现方式：

std::vector<std::size_t> parts(std::size_t m, std::size_t size)
{
    std::vector<std::size_t> res(size);

    for (std::size_t i = 0; i != m; ++i) {
        ++res[i % size];
    }
    return res;
}

std::size_t whichPart(std::size_t m, std::size_t size, std::size_t n)
{
    std::size_t index = 0;
    for (auto i : parts(m, size)) {
        if (n < i) {
            return index;
        }
        ++index;
        n -= i;
    }
    throw std::runtime_error("invalid argument");
}

- Jarod42

Answer 4

给定一个整数范围 [B, E)，最均匀（大小差异从不超过1）分割 N_bin 个箱子的方法是：

[⌊B＋E×N_numerator÷N_bin⌋, ⌊B＋E×(N_numerator＋1)÷N_bin)⌋ _{其中 Nnumerator＝0 到 (Nbin－1)}.

---

示例 - 获取像素范围以供多个线程使用：

for(unsigned int worker_index = 0; worker_index < n_workers; ++worker_index) {
    std::cout
        << "[" << n_pixels * worker_index / n_workers << ", "
        << n_pixels * (worker_index + 1) / n_workers << ")"
        << std::endl;
}

---

将区间[0,5)分成16个箱子

[0, 0)
[0, 0)
[0, 0)
[0, 1)
[1, 1)
[1, 1)
[1, 2)
[2, 2)
[2, 2)
[2, 3)
[3, 3)
[3, 3)
[3, 4)
[4, 4)
[4, 4)
[4, 5)

[0, 18) 划分为 16 个区间

[0, 1)
[1, 2)
[2, 3)
[3, 4)
[4, 5)
[5, 6)
[6, 7)
[7, 9)
[9, 10)
[10, 11)
[11, 12)
[12, 13)
[13, 14)
[14, 15)
[15, 16)
[16, 18)

将区间[0, 36152320)分成16个箱子。

[0, 2259520)
[2259520, 4519040)
[4519040, 6778560)
[6778560, 9038080)
[9038080, 11297600)
[11297600, 13557120)
[13557120, 15816640)
[15816640, 18076160)
[18076160, 20335680)
[20335680, 22595200)
[22595200, 24854720)
[24854720, 27114240)
[27114240, 29373760)
[29373760, 31633280)
[31633280, 33892800)
[33892800, 36152320)

- Константин Ван