| 1 |
// Copyright 2018-2023 Developers of the Rand project. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or |
| 4 |
// https://www.apache.org/licenses/LICENSE-2.0> or the MIT license |
| 5 |
// <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your |
| 6 |
// option. This file may not be copied, modified, or distributed |
| 7 |
// except according to those terms. |
| 8 |
|
| 9 |
//! Sequence-related functionality |
| 10 |
//! |
| 11 |
//! This module provides: |
| 12 |
//! |
| 13 |
//! * [`IndexedRandom`] for sampling slices and other indexable lists |
| 14 |
//! * [`IndexedMutRandom`] for sampling slices and other mutably indexable lists |
| 15 |
//! * [`SliceRandom`] for mutating slices |
| 16 |
//! * [`IteratorRandom`] for sampling iterators |
| 17 |
//! * [`index::sample`] low-level API to choose multiple indices from |
| 18 |
//! `0..length` |
| 19 |
//! |
| 20 |
//! Also see: |
| 21 |
//! |
| 22 |
//! * [`crate::distr::weighted::WeightedIndex`] distribution which provides |
| 23 |
//! weighted index sampling. |
| 24 |
//! |
| 25 |
//! In order to make results reproducible across 32-64 bit architectures, all |
| 26 |
//! `usize` indices are sampled as a `u32` where possible (also providing a |
| 27 |
//! small performance boost in some cases). |
| 28 |
|
| 29 |
mod coin_flipper; |
| 30 |
mod increasing_uniform; |
| 31 |
mod iterator; |
| 32 |
mod slice; |
| 33 |
|
| 34 |
#[cfg(feature = "alloc")] |
| 35 |
#[path = "index.rs"] |
| 36 |
mod index_; |
| 37 |
|
| 38 |
#[cfg(feature = "alloc")] |
| 39 |
#[doc(no_inline)] |
| 40 |
pub use crate::distr::weighted::Error as WeightError; |
| 41 |
pub use iterator::IteratorRandom; |
| 42 |
#[cfg(feature = "alloc")] |
| 43 |
pub use slice::SliceChooseIter; |
| 44 |
pub use slice::{IndexedMutRandom, IndexedRandom, SliceRandom}; |
| 45 |
|
| 46 |
/// Low-level API for sampling indices |
| 47 |
pub mod index { |
| 48 |
use crate::Rng; |
| 49 |
|
| 50 |
#[cfg(feature = "alloc")] |
| 51 |
#[doc(inline)] |
| 52 |
pub use super::index_::*; |
| 53 |
|
| 54 |
/// Randomly sample exactly `N` distinct indices from `0..len`, and |
| 55 |
/// return them in random order (fully shuffled). |
| 56 |
/// |
| 57 |
/// This is implemented via Floyd's algorithm. Time complexity is `O(N^2)` |
| 58 |
/// and memory complexity is `O(N)`. |
| 59 |
/// |
| 60 |
/// Returns `None` if (and only if) `N > len`. |
| 61 |
pub fn sample_array<R, const N: usize>(rng: &mut R, len: usize) -> Option<[usize; N]> |
| 62 |
where |
| 63 |
R: Rng + ?Sized, |
| 64 |
{ |
| 65 |
if N > len { |
| 66 |
return None; |
| 67 |
} |
| 68 |
|
| 69 |
// Floyd's algorithm |
| 70 |
let mut indices = [0; N]; |
| 71 |
for (i, j) in (len - N..len).enumerate() { |
| 72 |
let t = rng.random_range(..j + 1); |
| 73 |
if let Some(pos) = indices[0..i].iter().position(|&x| x == t) { |
| 74 |
indices[pos] = j; |
| 75 |
} |
| 76 |
indices[i] = t; |
| 77 |
} |
| 78 |
Some(indices) |
| 79 |
} |
| 80 |
} |