4

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?

Improve this question
3
  • Is it possible that this question fits better with gamedev.stackexchange.com ?
    – Myrddin Emrys
    Apr 4, 2012 at 23:44
  • @MyrddinEmrys: Why?
    – Dynamic
    Apr 6, 2012 at 18:41
  • 1
    Mostly because the description, though it never mentions a game, sounds very much like a game. Distributing unspecified 'resources' to 'targets' in an 'interesting' way. It's the phrase 'interesting'; people solving problems want even distributions or a specific pattern of distribution. But when you are creating problems (as in, a game) then you want it to be interesting. Of course I could be wrong, but this certainly sounds like game design to me. Even if its not, I wouldn't be surprised if he'd find a better mix of answers from game developers.
    – Myrddin Emrys
    Apr 6, 2012 at 19:29

2 Answers 2

Reset to default
6

Combine the two approaches. Hand out a random amount of the resource to a random user, then repeat. At each step, pick a portion of the remaining resource (1/x, with x a floating point number between 2 and 10), and hand it to any of the players (including a player who has already received some of the resource). When the remaining resource left to hand out gets low enough (say, under 1/2N left) just hand it out without further subdividing.

This allows for the chance of almost all of the resource going to the same player (1/2 handed out twice to one player), it being evenly divided, and a fractal-like distribution in between. Most of the time there will be significant imbalances in the resource available to each user. You can play with the cutoff point and the range of subdivision (2..10, 1..20, 3..5) to see how it varies the distribution of resources until you find a result that pleases you.

Further, the subdivision parameters could themselves be flexible... from A..B, and A and B are randomly chosen. If both are low (1.2 to 2.5) then a very small number of users will get most of the resources. If both are high (8.1 to 11.0) then the distribution will be quite even. This also allows for tuning the granularity of resource distribution as a setup option.

Improve this answer
0

IMHO it needs to figure out what probability distribution you want (looks like normal distribution would fit your requirements). You may let median to be R (choose it randomly each time) and you can also change variance each time. If speed is not that important, python's random module may generate random numbers according to the normal distribution. Otherwise, google for how to convert flat distribution to the normal distribution.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.