A generator (as I will use the term here) is an object that can “generate” other objects on demand. They work like random generators, except that they need not generate numbers or do so randomly: you ask it for the next value, and it gives it to you.
The naive generator is simply a class that supports this method:
Generators work a bit like iterators, but they are slightly different:
- Iterators work on both finite and infinite sequences, while generators are always (supposed to be) infinite.
- Iterators are typically used in loops to process elements in sequence on the spot. Generators are generally use over some time span (similar to how random numbers are often used in simulations).
- Iterators are usually restarted on each use; generators are rarely restarted.
Continue reading “Generators”
I finally laid my hands on Donald Knuth’s The Art of Computer Programming (what a wonderful set of books!), and found a neat algorithm for generating random integers 0, 1, 2, … , n – 1, with probabilities p_0, p_1, … , p_(n-1).
I have written about generating random numbers (floats) with arbitrary distributions for one dimension and higher dimensions, and indeed that method can be adapted for generating integers with specific probabilities. However, the method described below is much more concise, and efficient (I would guess) for this special case. Moreover, it is also easy to adapt it to generate floats for continuous distributions.
Continue reading “Generating Random Integers With Arbitrary Probabilities”
I have already covered how to generate random numbers from arbitrary distributions in the one-dimensional case. Here we look at a generalisation of that method that works for higher dimensions.
The basic trick, while easy to understand, is hard to put in words (without reverting to mathematical equations). For two dimensions, we divide the plane into slices. Each slice is a 1D distribution. We also calculate a distribution from summing the frequencies in each slice. The latter distribution gives us one coordinate, and the appropriate slice to use. The distribution of that slice then gives the second coordinate. All distributions are put into inverse accumulative response curves as was done to generate one-dimensional random numbers. (You should review that before implementing the 2D case).
In more dimensions, we also slice the space up into 1D distributions. Sums of these give us more distributions, which we can sum again, and again, until we reach a single distribution. This is used for the first coordinate, and to determine which distribution to use for the next coordinate. This goes on, until a 1D slice gives us the final coordinate. Again, all distributions are converted to inverse accumulative response curves.
If the above is unclear, I hope the detailed description below clears things up.
Continue reading “Generating Random Points from Arbitrary Distributions for 2D and Up”