How To Randomly Space Items ‘Just Enough’, Or How to Share Cookies Nicely With My Niece’s Kids

Posted on by

I was faced with an interesting problem lately in redoing my Sonar Eye and I realized I had forgotten a rather fundamental bit of code – how to randomly parcel out ‘just enough’ to do the job.

No, I don’t know what it’s called, which made Google a waste of time – but I remember first reading about it in Programming Pearls by Jon Bentley. Basically, you need it to randomly space out limited items somewhat evenly.

For example, say my Niece drops by with her two daughters, and I want to give them cookies. Lazy host that I am, I’m tempted to just give them a box and let them have at it. My niece however, is one of ‘those’ parents, so I have to be caring and disciplined about it – give them only some of the cookies from time to time, and don’t fill them up too fast (apparently, some people typically handle treats in such a miserly fashion).

So the rules are that I can give them five cookies in one hour, and not all at once. In fact, to avoid favoritism (or laziness), I have to give them the five cookies randomly, throughout the hour (note that I’m not being a bad host – they only need one cookie between them because these are absolutely enormous cookies).

That’s the problem in a nutshell. Of course, it seems simple: five cookies given to the girls over 1 hour means 1 cookie every twelve minutes. But I want random, so how about this: at the top of each minute I flip a coin and and give them a cookie if it’s heads?

It doesn’t take too long to see the problem here – at a 50/50 chance every minute, that’s approximately 30 heads/cookies in an hour. So what if I change the odds – say, 5 in 60? Still a problem, since no matter what odds I give, there is always a random chance I’ll give away too few or too many cookies – an intolerable situation for either side!

(By the way, if I was comfortable with approximate instead of exact, then 5/60 works – just pick a random number from 0-59 and see if it’s less than 5 – if it is, give a cookie. Over the long run, it will give out a cookie about 5/60th of the time – but of course it could sometimes give out 1 cookie or 10 over the course of an hour. Such is the problem with approximately…)

What I need is to parcel an exact number of cookies in a give time – no more, no less. The Programming Pearls solution is embarrassingly simple to describe, if a bit tricky to program right:

  • Let A be the number of items to give out = 5 cookies.
  • Let B the number of intervals we test = 60 (minutes).
  • At every interval grab a random number and compare it to A/B, and if A/B is greater, it’s cookie time.
  • Decrease A by 1 for every success.
  • And decrease B by 1 at every interval.

Of course, the random number needs to be in relation to its maximum value for this to work (after all, 9 is a large random number if the max is 10, but a small one if the max is 65536). So the comparison becomes:

if (A/B>RANDOM/RANDOMMAX)

And if you want to minimize divides for speed, or are using integer math (where RANDOM/RANDOMMAX is always 0, since RANDOM<RANDOMMAX):

if (A*RANDOMMAX/B>RANDOM)

If the random number is too big, no cookies. But if less, we give out a cookie AND reduce A by 1:

if (A/B>RANDOM/RANDOMMAX)
A=A-1
GiveCookie()

But in every case, decrease B

B=B-1

Put together (and reworked into Arduino C, which is where I’m using it):

int DoWeGetCookies(void) // call at the top of each minute
{
  static int a=5,b=60;
  if (b<=0)
  {
    return -1; // our flag for end of hour/done
  }
  if (a*60/b>random(60))
  {
    --a;
    --b;
    return 1;
  }
  --b;
  return 0;
}

To see that it works, consider some calls:

  • At the beginning, a cookie is 5/60 likely to be picked, then 5/59, 5/58 etc – each pass slightly improving the odds.
  • Obviously if the cookie still hasn’t been picked near the end it becomes 5/7, then 5/6, then 5/5, which guarantees it will be picked with 100% probability, as 5/5>random(60)/60 (note that the Arduino’s random function, like many, is exclusive of the top boundary, so random(60) will never go any higher than 59, meaning it will never get higher than 59/60, which is less than 5/5).
  • On the other hand, if it’s picked, then A is reduced, and A/B becomes 4/59, 4/58, etc and (worse case) eventually 4/4 and then a guaranteed pick.
  • …Or that gets picked, and then it’s 3/58, 3/57, and so on.
  • Finally, what if all cookies are picked before 60 minutes is up? Then the fraction becomes 0/20 or 0/10 or whatever, preventing any more picks from succeeding, since 0 will never be more than any random number pick.

Using this algorithm, the result is a randomly distributed spread of cookies throughout the hour – and the perfect number of them, no less.

Here are some variations in using this code:

  • What if I want to pick 5 numbers from a list of 60 numbers with equal probability? Fill an array with numbers, walk along the array (rather than waiting for a the top of each minute in our cookie example) and run the same calculation. You’ll end up with those 5. As a side benefit, there will be no repeats.
  • And by using an array, the selections can be anything – numbers, words, objects, etc. For example, use 5 and 54 instead of 5 and 60 and you can use the array for cards, dealing out a hand without repeats.
  • You can even dispense with the array – for example, if you count from 0 to 59 and the digits you want are 0-59 just return each index. Or if there is a pattern to the values then you can use a formula to convert the index to your value.

Of course, when you have room for an array, picking from a list has easier methods (like shuffling a list and picking the first N items). Where this algorithm works best is when you have limited array space (like an Arduino), or need to pick across an interval and the result is an either/or choice – something or nothing – and there is a fixed limit on the number of successes you can have.

Kinda like cookies handed out over an hour…

Comments are closed.