Sampling and shuffling v0.1.0
Shuffle<G, T>
pub func Shuffle<G: RandomGenerator, T>(
generator: &var G,
items: var T[..]
)
Shuffles items into a uniformly random order.
Fisher and Yates' method, walking from the end and swapping each position with one at or below it. The bound
is what makes it uniform: swapping with a position anywhere in the collection is the version that is subtly
biased, and it is the version almost everyone writes first.
Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
G: RandomGenerator | the generator's type |
T | the item type |
Parameters
| Name | Type | Description |
|---|---|---|
generator | &var G | where the bits come from |
items | var T[..] | the sequence to shuffle in place |
ChooseIndex<G>
pub func ChooseIndex<G: RandomGenerator>(
generator: &var G,
count: uint
) -> uint
A uniformly chosen index below count, or count itself when there is nothing to choose from.
Returning the count for an empty collection gives the caller a value that cannot be mistaken for a valid
index, which a zero would be.
Type parameters
| Name | Description |
|---|---|
G: RandomGenerator | the generator's type |
Parameters
| Name | Type | Description |
|---|---|---|
generator | &var G | where the bits come from |
count | uint | how many there are to choose among |
Returns: an index in [0, count), each equally likely
WeightedIndex<G>
pub func WeightedIndex<G: RandomGenerator>(
generator: &var G,
weights: float64[..]
) -> uint
An index chosen in proportion to weights.
A weight of zero is never chosen; negative weights are treated as zero rather than subtracting from the
total, since a negative probability has no meaning and silently reversing a comparison is worse than
ignoring the entry. Weights that are all zero, or an empty slice, give the length — the same
out-of-range answer ChooseIndex gives for an empty collection.
Runs in time proportional to the length, reading the weights twice: once to total them and once to select.
Type parameters
| Name | Description |
|---|---|
G: RandomGenerator | the generator's type |
Parameters
| Name | Type | Description |
|---|---|---|
generator | &var G | where the bits come from |
weights | float64[..] | the relative weight of each index; they need not sum to one |
Returns: an index chosen in proportion to its weight