Randomly put elements into N buckets

Question

I have a bag with 100 potatoes. I need to split the potatoes in N number of buckets. In each bucket I must have between 15 and 60 potatoes.

Obviously, I need a step by step solution to make this into code.

The best way that I have so far:

Minimum number of buckets: 100/60 = 1 (40) => round it up => 2
Maximum number of buckets: 100/15 = 6 (10) => round it down => 6

So you can have a minimum of 2 and maximum of 6 buckets. Now we pick a random number (because I need only one solution, not all of them).

Let's pick 3.
Potatoes per bucket: 100/3 = 33 (1)
Buckets: 33, 33, 34.

Now here is the tricky part. While this IS a solution to the original problem, it doesn't work for me, because I need the numbers to be more random than that. In the problem the condition was 15-60 but here we get only 33-34, which is too uniform for what I need.

One of the solutions from here could be to start adding and subtracting numbers from each bucket. Probably do this for 10 iterations or so, but I reckon there must be a better way to do it.

Any ideas?

Answer 1

ElKamina's answer is likely correct, but for the mathematically-challenged here is another potato-sorting algorithm.

from random import randint, choice

def random_distribution(num_potatoes, num_buckets, min_num_potatoes, max_num_potatoes):
    """
    Distributes a set number of potatoes randomly across a number of buckets
    such that each bucket has a number of potatoes within a certain range.
    """
    # Cache the starting value
    _num_potatoes = num_potatoes

    # Create some buckets to put potatoes in, initial value 0
    buckets = [0 for x in range(num_buckets)]

    # Get a list of which buckets are not too empty or too full--
    # All of them are valid choices at this point
    indices = [i for (i, value) in enumerate(buckets)]

    # Distribution loop-- continue until we run out of potatoes or the
    # buckets are too full to keep adding to them.
    while indices and num_potatoes and sum(buckets) <= (max_num_potatoes * num_buckets):

        # Pick a random bucket from the list of eligible buckets
        index = choice(indices)

        # Add a potato to it
        buckets[index] = buckets[index] + 1
        num_potatoes = num_potatoes - 1

        # Refresh the list of eligible buckets
        indices = [i for (i, value) in enumerate(buckets) if (value < min_num_potatoes) or (value < max_num_potatoes)]

    print('Of %(potatoes)i potatoes distributed across %(buckets)i buckets, each having at least %(min)i and at most %(max)i, our spread looks like %(spread)s (total bucketed: %(sum)i).' % {
        'potatoes': _num_potatoes,
        'buckets': num_buckets,
        'min': min_num_potatoes,
        'max': max_num_potatoes,
        'spread': buckets,
        'sum': sum(buckets)
    })
    return buckets

for x in range(10):
    random_distribution(100, 3, 15, 60)

Example outputs:

Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [35, 37, 28] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [29, 36, 35] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 27, 41] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [33, 33, 34] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 32, 36] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [37, 28, 35] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 27, 41] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [39, 27, 34] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 30, 38] (total bucketed: 100).
Of 100 potatoes distributed across 3 buckets, each having at least 15 and at most 60, our spread looks like [32, 30, 38] (total bucketed: 100).

With your given example, if you want more disparity in values you need to start with fewer potatoes or use more buckets.

Answer 2

First, note that you can simplify a bit your problem. Instead of "each bucket needs to contain between 15 and 60 potatoes and the total in the buckets should be 100" you can restate as "I need n numbers between 0 and 45 (60 - 15) such that these numbers sum up to 100 - n x 15". In other words, fill all your buckets with 15 potatoes, and now you are trying to decide how to use the remaining potatoes to fill the remaining space in your buckets.

Suppose that you have n buckets to fill, and p potatoes left. Generate a random number r between 0 and 45, you are now left with p - r potatoes. Can you now fill the remaining (n-1) buckets?

• If (p - r) < 0, you obviously cannot fill the remaining buckets, because you allocated more than what you have,
• If (p - r) > 45 * (n - 1), this is not feasible: you have too many potatoes left, and would have to exceed the capacity of your buckets.
• Otherwise, you know that if you put r potatoes in the current bucket, you will still be able to find a solution for the next buckets.

You can write this as a recursive solution: for each successive bucket, generate a random number of potatoes until that number does not prevent you from finding a solution at the next step.

Below is a very crude F# implementation, which can obviously be refined/optimized but illustrates the gist of the algorithm. allocation is a list of int containing the quantity already allocated to buckets, qty is the Quantity of potatoes left to allocate, buckets the number of buckets left and min, max the capacity of buckets. For instance with 100 potatoes and 3 buckets, you would call solve 100 3 15 60.

The resulting allocation should be "as random as it gets", i.e. it should produce with equal probability any possible allocation, with one caveat: I assumed the order of the buckets doesn't matter. Given that the algorithm allocates the remaining potatoes based on what was allocated so far, depending on the path, the "head" of the list is constrained, and the allocation will likely allocate more on the first buckets. If you wanted to have a "true" random allocation, you would need to shuffle the buckets once the allocation is finished.

Hope this helps!

let rng = new System.Random() 

let rec allocate allocation qty buckets min max =
      match buckets with
      | 0 -> allocation
      | 1 -> qty :: allocation
      | _ ->
         let candidate = rng.Next(min, max + 1) // try a number in [min,max]
         let rest = qty - candidate
         if rest < (buckets - 1) * min // not enough left
         then allocate allocation qty buckets min max // try again
         else if rest > (buckets - 1) * max // too much left
         then allocate allocation qty buckets min max // try again
         else allocate (candidate :: allocation) rest (buckets - 1) min max

let solve qty buckets min max =
   if min * buckets > qty then failwith "unfeasible"
   if max * buckets < qty then failwith "unfeasible"
   allocate [] qty buckets min max

Answer 3

First, distribute the minimum numbers needed. In your example put 15 into each bucket. If you have 3 buckets, you will have put 45 into 3 equally. Remaining (R): 55. Remaining capacity for each bucket (C1,C2,C3):45.

Pick a number k (see footnote on how to pick k). If it is greater than R, then set it to R (k=min(k,R) ). Pick a bucket i randomly. If Ci is less than, k set k to Ci ( k=min(k,Ci) ). Now put k potatoes into bucket i. Update R and Ci (R=R-k, Ci=Ci-k). Repeat this until all the potatoes are finished (R=0).

Footnote: Picking k

You can either set k=1 or choose k from any appropriate distribution (eg: choose k randomly from 1 to 10 ).

Code

import random
def distPotato(R, N, minP, maxP):
    C = [maxP-minP for i in range(N)]
    V = [minP for i in range(N)]
    R-=sum(V)    
    while(R>0):
        k = random.choice(range(10)) + 1
        i = random.choice(range(N))
        k = min(k,R)
        k = min(k, C[i])
        C[i]-=k
        R-=k
        V[i]+=k
    return V

distPotato(100,3,15,60)

Answer 4

I suggest just randomly filling buckets with between 15 and 60 potatoes until you have less than 15 potatoes left. Then take the last bucket you filled, try to put your remaining potatoes in that bucket. If it's less than 60, great! If it's more than 60, split the bucket in half.

So lets say you do this a few times and you end up with 74 potatoes. You now fill a bucket with a random number fo potatoes. Let's say it's 60. You now have 14 potatoes left, too few for another bucket but too many to put into your last bucket. Simple, pour out the previous bucket (74 potatoes, again) then make two buckets of 37 each.

The problem is that your last two buckets won't be random (or at least not "as random", if you will) as the other buckets but because you can't have less than 14 potatoes in a bucket, there is nothing you can do about it.

Answer 5

I imagine a length of beef in a butcher shop, and the butcher is asked to cut it into N pieces of that random size in as little time as possible.

His first action would likely be to randomly whack away at the meat, making sure to not slice it too close to his previous slice or to the edges until he has made N-1 cuts.

For your purposes, the slab of beef could instead be a line of potatoes.

So to translate this into psuedo-code:

initiate a list of chosen potatoes to empty
while you have chosen less than N-1 potatos
    pick a potato
    if the potato is less than 15 potatoes away from a side
        continue
    if the potato is less than 15 potatoes away from a chosen potato
        continue
    add this potato to the chosen list
sort the chosen list
split the line of potatoes using the chosen potatoes as delimeters