Take the 2-minute tour ×

Given the vector size N, I want to generate a vector <s1,s2, ..., sn> that s1+s2+...+sn = S.

Known 0<S<1 and si < S. Also such vectors generated should be uniformly distributed.

Any code in C that helps explain would be great!

share|improve this question
One trivial solution is to iteratively generate numbers in range (0,S-sum) where sum is the sum of all so far generated numbers, and then shuffle the list. Don't think it is uniform enough though. :| –  amit Sep 27 '12 at 7:32
One question: Are the elements s1,s2,...sn given from an input vector? If so - the problem is equivalent to the subset-sum problem, we cannot know efficiently if there is a set of numbers that sums to S in a given vector, let alone find a random sample of size n of them. –  amit Sep 27 '12 at 8:36
add comment

2 Answers

up vote 1 down vote accepted

The code here seems to do the trick, though it's rather complex.

I would probably settle for a simpler rejection-based algorithm, namely: pick an orthonormal basis in n-dimensional space starting with the hyperplane's normal vector. Transform each of the points (S,0,0,0..0), (0,S,0,0..0) into that basis and store the minimum and maximum along each of the basis vectors. Sample uniformly each component in the new basis, except for the first one (the normal vector), which is always S, then transform back to the original space and check if the constraints are satisfied. If they are not, sample again.

P.S. I think this is more of a maths question, actually, could be a good idea to ask at http://maths.stackexchange.com or http://stats.stackexchange.com

share|improve this answer
The probability of n numbers reach sum of exactly S with real distribution is 0. With floating point it is in the neighborhood of 2^-50. While the idea might be OK for integers - it fails miserably for real numbers. –  amit Sep 27 '12 at 8:30
I see.. I seem to have misread the question. –  Qnan Sep 27 '12 at 8:31
@amit See the edit –  Qnan Sep 27 '12 at 8:39
Seems nice, but it does not seem to be the "rejection sampling" from first look. Could you also add a short description on the method how it is done? The "abstract" there is not informative enough to understand how to implement it. –  amit Sep 27 '12 at 8:42
Yep, right. Wrote down the rejection-based algorithm sketch. –  Qnan Sep 27 '12 at 8:58
show 4 more comments

[I'll skip "hyper-" prefix for simplicity]

One of possible ideas: generate many uniformly distributed points in some enclosing volume and project them on the target part of plane.

To get uniform distribution the volume must be shaped like the part of plane but with added margins along plane normal.

To uniformly generate points in such volumewe can enclose it in a cube and reject everything outside of the volume.

  1. select margin, let's take margin=S for simplicity (once margin is positive it affects only performance)
  2. generate a point in cube [-M,S+M]x[-M,S+M]x[-M,S+M]
  3. if distance to the plane is more than M, reject the point and go to #2
  4. project the point on the plane
  5. check that projection falls into [0,S]x[0,S]x[0,S], if not - reject and go to #2
  6. add this point to the resulting set and go to #2 is you need more points
share|improve this answer
add comment

Your Answer


