What's a good algorithm for a random, uneven distribution of a fixed amount of a resource?

Posted by NickC on Programmers See other posts from Programmers or by NickC
Published on 2012-04-04T23:08:25Z Indexed on 2012/04/04 23:42 UTC
Read the original article Hit count: 242

Filed under:
|

Problem

I have X, a positive integer, of some resource, R.

There are N potential targets.

I want to distribute all of R to the N targets in some "interesting" way.

"Interesting" means:

  • Some targets may not get any R.
  • It should rarely be near even (with a majority of target getting near X/N of the resource).
  • There should be at least a small chance of one target getting all of R.

Bad solutions

The naive approach would be to pick a random target and give one R to it and repeat X times. This would result in too even of an approach.

The next idea is to pick a random number between 1 and X and give it to a random target. This results in too large of a number (at least X/2 on average) being given to one target.

Question

This algorithm will be used frequently and I want the distribution to be interesting and uneven so that the surprise doesn't wear off for users.

Is there a good algorithm for something in between these two approaches, that fits the definition of interesting above?

© Programmers or respective owner

Related posts about algorithms

Related posts about random