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 20136 days, 4 hours, 28 minutes ago.