Geek asks and answers

Randomly place items in N buckets

I have a bag with 100 potatoes. I need to break the potatoes into N number of buckets. In each bucket I have to have from 15 to 60 potatoes.

Obviously, I need a step-by-step solution to do this in code.

The best way I have so far is:

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

Thus, you can have at least 2 and maximum 6 buckets. Now we select a random number (because I need only one solution, not all).

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

Now here is the hard part. Although this is a solution to the original problem, it does not work for me, because I need the numbers to be more random than this. The condition was 15-60 in the problem, but here we get only 33-34, which is too even for what I need.

One solution here would be to add and subtract numbers from each bucket. Probably do it for 10 iterations or so, but I believe there should be a better way to do this.

Any ideas?

+3
source share
4 answers

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

k (. , k). R, R (k = min (k, R)). . Ci , k k Ci (k = min (k, Ci)). k i. R Ci (R = R-k, Ci = Ci-k). , (R = 0).

: k

k = 1, k (: k 1 10).

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)
+2

, N .

, , , , N-1.

.

, psuedo-:

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
0

15 60 , 15 . , , . 60, ! 60, .

, , , 74 . . , 60. 14 , , , . , (74 , ), 37 .

, (, , " ", ), , , 14 , .

0

-, , . " 15 60 , 100", " n 0 45 (60 - 15), 100 - nx 15". , 15 , , , .

, n , p . r 0 45, p-r. (n-1) ?

  • (p - r) < 0, , , , , ,
  • (p - r) > 45 * (n - 1), : , .
  • , r , .

: , .

​​ F #, , , /, . - int, , , qty - , , , . , 100 , 100 3 15 60.

The resulting distribution should be "as random as it turns out", that is, it should give with equal probability any possible distribution with one caveat: I suggested that the order of the buckets does not matter. Given that the algorithm allocates the remaining potatoes based on what has been allocated so far, depending on the path, the "head" of the list is limited, and the distribution is likely to allocate more to the first buckets. If you want to have a “true” random distribution, you will need to shuffle the buckets after the selection is complete.

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
0
source

More articles:


All Articles