如何将数字划分为未定义的随机数量的块，每个块都是最小和最大大小内的随机大小？

Question

我使用的是 C#，但这更多的是逻辑问题而不是语言问题。我很困惑。我发现了类似的问题，例如“this one”，但区别在于，在形成最后一个块之前，我不知道有多少块。我一开始唯一知道的是项目的总数，以及项目块的最小和最大大小。 假设我有一个 int TotalItems = 15。我想将其分成 3 到 5 之间随机大小的块。任何块都不应超出该范围，并且没有剩余部分。 因此，一些有效的结果包括：

5,5,5

3,3,3,3,3

5,4,3,3

但问题是，每当选择倒数第二个块时，它都必须考虑最后一个块会剩下什么。例如： 如果前 3 个块是 3,5,5（所有有效大小），则只剩下 2 个块，因此第 3 个块应该不大于 4，这样剩余的块将不少于 3。

这是我到目前为止不起作用的：

private List<int> SplitIntoChunks(int totalItems, int minChunkSize, int maxChunkSize)
    {
        List<int> chunks = new();

        int remainingItems = totalItems;

        while (remainingItems > 0)
        {
            int chunkSize;

            if (remainingItems == minChunkSize)
            {
                chunkSize = minChunkSize;
            }
            else
            {
                chunkSize = Random.Range(minChunkSize, Mathf.Min(maxChunkSize, remainingItems) + 1);

                if (remainingItems - chunkSize < minChunkSize)
                {
                    chunkSize = remainingItems; // This sometimes results in chunkSize larger than maxChunkSize.
                }

                if (remainingItems - chunkSize > maxChunkSize)
                {
                    chunkSize = maxChunkSize; // This then sometimes results in a remainder that is too small for the next chunk.
                }
            }

            chunks.Add(chunkSize);

            remainingItems -= chunkSize;
        }

        return chunks;
    }

Answer 1

对于可能的输入，可以像这样找到一种解决方案。我们仅添加最小大小的块，然后在它们之间分配剩余部分。如果余数不完全适合，则该问题在此类输入上无法解决。

List<int> SplitIntoChunks(int totalItems, int minChunkSize, int maxChunkSize)
{
    int chunksCount = totalItems / minChunkSize;
    int remainder = totalItems % minChunkSize;

    if ((maxChunkSize - minChunkSize) * chunksCount < remainder) 
        throw new Exception("unsolvable");

    var chunks = Enumerable.Repeat(element: minChunkSize, count: chunksCount).ToList();

    for(int i = 0; i < chunksCount; ++i)
    {
        if (remainder == 0) break;

        int addition = Math.Min(maxChunkSize - minChunkSize, remainder);
        chunks[i] += addition;
        remainder -= addition;
    }

    return chunks;
}

然后，如果需要随机性，可以随机修改初始解。