I have a set of objects, and each object has (let's say) a color. Given a distribution such as:

red : 50%
green : 30%
blue : 20%

I need to produce an N-length array of objects with a color distribution as close to this as possible. It is possible that the length of the original list is smaller than N, so duplicates may be required.

Is there an efficient algorithm that might be suited for this kind of task? I imagine there is, but I'm lacking the terminology to find it.


The term you are looking for is "sampling", "sampling without replacement", "sampling with replacement", "generating random samples from a given distribution", or "inverse transform sampling". Lots of nice articles and references can be found if you use those keywords to search.

Here is a simple algorithm to simulate the given distribution, red:50% green:30% blue:20%, using sampling with replacement.

Let arr be an empty array. 
Repeat the following N times
    generate a random float-point number between 0 inclusive and 1 exclusive.
        if the number is between 0 inclusive and 0.50 exclusive, select a random red object.
        if the number is between 0.50 inclusive and 0.70 exclusive, select a random green object.
        if the number is between 0.70 inclusive and 1.0 exclusive, select a random blue object.
    Append the selected object to arr.
Return arr. 
  • $\begingroup$ Thanks for the terminology, just what I needed. $\endgroup$ – Graham Aug 5 at 15:06

Do you need to guarantee that, in every sample, 50% of the objects are red, 30% are green and 20% are blue? If so, just make your array consist of $0.5\,N$ red objects chosen uniformly at random, followed by $0.3\,N$ green and $0.2\,N$ blue. You'll need to deal with the rounding error if $N$ isn't divisible by $10$. You can always shuffle the array if it's not desirable to have it sorted by colour.

If you only need to guarantee that the proportions of the colours are correct in the long-run, Apass.Jack's solution will do the job. If $N$ is very large, then each array generation is "the long-run" and will be close to the correct proportions (but not guaranteed to be exact).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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