dimanche 3 janvier 2016

Represent a number as a uniformly random sum of N numbers in 0..maxSummand

There can be infinite ways to represent a positive number as a sum of numberOfSummands positive summands each of which doesn't exceed maxSummand. I need a way to generate one of those representations roughly uniformly for given sum, numberOfSummands and maxSummand, i.e. that any possible list of N summands can be returned with roughly equal probability (as far as double floating point precision allows it).

Example:

asSummands(sum = 41.0, numberOfSummands = 3, maxSummand = 22.0, prng = somePRNG())

could return:

[18.3, 5.8, 16.9]

(There will certainly be more digits after the dot in an actual generated list.)

I can ignore the fact that it is not possible to reach a certain sum with certain summands (e.g. you can't achieve the sum of 10.0 with 4 summands if maxSummand is 2.0), assume the algorithm is never called with such arguments.

I also assume that the PRNG generates numbers uniformly.

I could only come up with a solution that is far from uniform:

Chop the sum into numberOfSummands equal summands, pick pairs of them and, for each pair, transfer a random amount from one element of the pair to the other element, so the overall sum doesn't change, then shuffle the summands. It works with an even number of summands, and I can modify it to work with an odd number of summands, but the solution feels quite dumb, I feel there could be a more natural way.




Aucun commentaire:

Enregistrer un commentaire