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