Search code examples
algorithmmathrandom

How to divide a number into an undefined random number of chunks, with each chunk being a random size within a min and max size?


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


Solution

  • 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:

    • possible lengths are 3, 4, 5, chose one, say 4 (if you know the length at beginning, you will then know if you can solve the problem or not)
    • construct (3,3,3,3), total is 12, there is 3 units to distribute in it
    • let say you chose to add one at (random chose) first position then get (4,3,3,3)
    • let say you chose to add one at (random chose) fourth then get (4,3,3,4)
    • chose one at random and add one, let say you chose position fourth, you then get (4,3,3,5) Beware not to consider positions already filled with maxSize at each round.