Download or view randomDistribution.frink in plain text format
use binarySearch.frink
/** This class generates random elements from a discrete set with a
known distribution, for example, the frequency of letters in the English
language.
HOWEVER, when generating random items, it is O(log n) with a
worst case of O(n) (where n is the number of items to be chosen from).
For a better constant-time algorithm, see DiscreteDistribution.frink .
However, an O(1) efficient algorithm can be found in the
DiscreteDistribution.frink sample program.
*/
class randomDistribution
{
// An array of elements
var elements
// The sum of probabilities
var sum
new[] :=
{
elements = new array
sum = 0
}
// Adds an item with the specified probability.
add[item, prob] :=
{
sum = sum + prob
elements.push[ [item, prob, sum] ]
}
// Selects a random item based on the specified probabilities.
random[] :=
{
z = randomFloat[0, sum]
index = binarySearch[elements, z, {|a,b| a <=> b@2}]
return elements@index@0
}
}
Download or view randomDistribution.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19966 days, 21 hours, 59 minutes ago.