malachite_base/foer_sequences/
random.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::foer_sequences::FoerSequence;
10use crate::num::random::geometric::GeometricRandomNaturalValues;
11use crate::random::Seed;
12use crate::vecs::random::{RandomVecs, random_vecs};
13
14/// Generates random [`FoerSequence`]s, given an iterator of random elements.
15///
16/// This `struct` is created by [`random_foer_sequences`]; see its documentation for more.
17#[derive(Clone, Debug)]
18pub struct RandomFoerSequences<I: Iterator>(
19    RandomVecs<I::Item, GeometricRandomNaturalValues<u64>, I>,
20)
21where
22    I::Item: Eq;
23
24impl<I: Iterator> Iterator for RandomFoerSequences<I>
25where
26    I::Item: Eq,
27{
28    type Item = FoerSequence<I::Item>;
29
30    fn next(&mut self) -> Option<FoerSequence<I::Item>> {
31        Some(FoerSequence::from_vecs(
32            self.0.next().unwrap(),
33            self.0.next().unwrap(),
34        ))
35    }
36}
37
38/// Generates random [`FoerSequence`]s whose non-repeating and repeating components have a specified
39/// mean length, with elements from a given iterator.
40///
41/// The input iterator must be infinite, but this is not enforced.
42///
43/// The output length is infinite.
44///
45/// # Expected complexity per iteration
46/// $T(i) = O(m^{1+\varepsilon} T^\prime(i))$ for all $\varepsilon > 0$
47///
48/// $M(i) = O(m M^\prime(i))$
49///
50/// where $T$ is time, $M$ is additional memory, $i$ is the iteration number, $m$ is
51/// `mean_length_numerator / mean_length_denominator`, and $T^\prime$ and $M^\prime$ are the time
52/// and memory functions of the iterators produced by `xs_gen`: the non-repeating and repeating
53/// parts have geometrically-distributed lengths with mean $m$, and reducing the sequence finds the
54/// repeating part's minimal period.
55///
56/// # Panics
57/// Panics if `mean_length_numerator` or `mean_length_denominator` are zero, or, if after being
58/// reduced to lowest terms, their sum is greater than or equal to $2^{64}$.
59///
60/// # Examples
61/// ```
62/// use itertools::Itertools;
63/// use malachite_base::foer_sequences::random::random_foer_sequences;
64/// use malachite_base::foer_sequences::FoerSequence;
65/// use malachite_base::num::random::random_primitive_ints;
66/// use malachite_base::random::EXAMPLE_SEED;
67///
68/// assert_eq!(
69///     random_foer_sequences(EXAMPLE_SEED, &random_primitive_ints::<u8>, 4, 1)
70///         .take(10)
71///         .map(|x| FoerSequence::to_string(&x))
72///         .collect_vec(),
73///     &[
74///         "[[85, 11, 136, 200, 235, 134, 203, 223, 38, 235, 217, 177, 162, 32]]",
75///         "[166, 234, 30, 218, [90, 106, 9, 216]]",
76///         "[204]",
77///         "[151, 213, 97, 253, 78, [91, 39]]",
78///         "[191, 175, 170, 232]",
79///         "[233, 2, 35, 22, 217, 198]",
80///         "[[114, 17, 32, 173, 114, 65, 121, 222, 173, 25, 144]]",
81///         "[148, 79, 115, 52, 73, 69, 137, 91]",
82///         "[153, 178, 112]",
83///         "[34, 95, 106, 167, 197, [130, 168, 122, 207, 172, 177, 86, 150, 221]]"
84///     ]
85/// )
86/// ```
87pub fn random_foer_sequences<I: Iterator>(
88    seed: Seed,
89    xs_gen: &dyn Fn(Seed) -> I,
90    mean_length_numerator: u64,
91    mean_length_denominator: u64,
92) -> RandomFoerSequences<I>
93where
94    I::Item: Eq,
95{
96    RandomFoerSequences(random_vecs(
97        seed,
98        xs_gen,
99        mean_length_numerator,
100        mean_length_denominator,
101    ))
102}
malachite_base/foer_sequences/random.rs

malachite_base/foer_sequences/
random.rs
