CODEWITHSUNDEEP
algorithmrandomconstraints
Mykhailo Granik
Mykhailo Granik

Reputation: 378

Generate list of real values, which sum up to fixed value and satisfy some constraints

I need to generate n random real values P[0], P[1], ..., P[n-1] which satisfy the following constraints:

Pmin[0] <= P[0] <= Pmax[0]
Pmin[1] <= P[1] <= Pmax[1]
...
Pmin[n-1] <= P[n-1] <= Pmax[n-1]

P[0] + P[1] + ... + P[n-1] = S

Any idea how to do this efficiently?

Upvotes: 1

Views: 175

Answers (2)

comocomocomocomo
comocomocomocomo

Reputation: 4942

For every i, assign P[i] := Pmin[i]
Compute the sum
If sum>S, then stop (it's impossible)
For every i:
    If P[i]+S-sum <= Pmax[i]
        P[i] = P[i]+S-sum
        Stop (it's done :-)
    sum = sum+Pmax[i]-P[i]
    P[i] = Pmax[i]
    Go for next i
Stop (it's impossible)

Ooops, sorry, you said random... that's not so trivial. Let me think about it...

Run the previous algorithm to have a starting point. Now compute the total margin above and below. The margin above is the sum of individual margins Pmax[i]-P[i] for every i. The margin below is the sum of individual margins P[i]-Pmin[i] for every i.

Traverse all the elements but one in a random order, visiting each one of them exactly once. For every one of them:

  • Update the margin above and the margin below subtracting from them the contribution of the current element.
  • Establish a min and max for the current value taking into account that:
    • They must be in the interval [Pmin[i], Pmax[i]] AND
    • These min and max are near enough to P[i], so that changing other elements later can compensate changing P[i] to this min or max (that's what the margins above and below indicate)
    • Change P[i] to a random value in the calculated interval [min, max] and update the sum and the margins (I'm not 100% sure of how the margins should be updated here...)

Then adjust the remaining element to fit the sum S.

Regarding the traversal in random order, see the Knuth shuffles.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28292

In general, it is not possible to solve this problem if choosing elements uniformly at random from the given ranges.

Example 1: Say that Pmin[i] = 0 and Pmax[i] = 1. Say that n = 10 and S = 100. Then there is no solution, since the greatest possible sum is 10.

Example 2: Say that Pmin[i] = 0 and Pmax[i] = 1. Say that n = 10 and S = 10. Then there is exactly one solution: choose P[i] = 1.

It is possible to write an algorithm such that the resulting sequence is chosen uniformly at random from the set of possible solutions; this is quite different from saying that the P[i] are uniformly distributed between Pmin[i] and Pmax[i].

The basic idea is to, at each stage, further restrict your range, as follows:

  1. The beginning of the range ought to be the larger of the following two quantities: Pmin[i], or S - Smax[i] - P, where Smax[i] is the sum Pmax[i+1] + ... + Pmax[n] and P is the sum P[0] + ... + P[i]. This guarantees that you're picking a number large enough to eventually work.
  2. The end of the range ought to be the smaller of the following two quantities: Pmax[i], or S - Smin[i] - P, where Smin[i] is the sum Pmin[i+1] + ... + Pmin[n] and P is as before. This guarantees that you're picking a number small enough to eventually work.

If you are able to obey those rules when picking each P[i], there's a solution, and you will find one at random. Otherwise, there is not a solution.

Note that to actually make this select solutions at random, it's probably best to shuffle the indices, perform this algorithm, and then rearrange the sequence so that it's in the proper order. You can shuffle in O(n), do this algorithm (recommend dynamic programming here, since you can build solutions bottom-up) and then spit out the sequence by "unshuffling" the resulting sequence.

Upvotes: 1

Related Questions