I'm using C# but this is more of a logic question than a language question. I'm stumped. I've found similar questions such as this one but the difference being I won't know how many chunks until the last chunk is formed. The only thing I know at the start is the total number of items, and the min and max size of chunks of items. Say I have an int totalItems = 15. I want to divide it into chunks that are a random size from 3 to 5. None of the chunks should be outside that range, and no remainder.
So some valid outcomes include:
5,5,5
3,3,3,3,3
5,4,3,3
But the problem is whenever selecting the second-to-last chunk it has to consider what will be left over for the last chunk. For instance: If the first 3 chunks are 3,5,5 (all valid sizes) there is only 2 left, so the 3rd chunk should have been no larger than 4, so that the remainder would be no less than 3.
Here's what I've got so far which isn't working:
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;
}
Get random chunks until there is a remainder (if there is no you win). Say the remainder is n<minSize
, then there is missing minSize-n
units, so pick these units in the list of know chunks that have size >minSize
.
Ex.: You want to split 15, and found (3,5,5;2). You then need to pick one (3-2) in one of the 5's, say (3,5,4;3).
This splitting may also be completed a little bit more to get a truly random splitting. Now that you have (3,5,4,3) you can determine which are the possible value for the last: maxSize=5
actual remainder is 3
then you may try to pick at most 2 more units. As there is 3 units that can be transfered to the last, values at the end may be 3, 4 or 5. Pick one at random, then complete as previously. Say you randomly chose 4 to be at the end, then find a unit in (3,5,4;3), say (3,4,3;4).
You may also use another algorithm. Roughly. Determine that there is at least 15/5 chunks at most 15/3, chose a length (randomly or not depends on your needs), fill it with 3's and then distribute what remains randomly:
maxSize
at each round.