sim_lib_discrete_comb/
word.rs

1//! Fixed-alphabet words, cyclic patterns, and longest-only selection.
2//!
3//! Words are produced lazily in mixed-radix lexicographic order. The first
4//! position is most significant, so rank `0` is the all-zero digit word and the
5//! last position changes fastest.
6
7// conformance: finite enumeration adapters preserve rank/unrank and lazy limits.
8
9use crate::{CombError, mixed_radix_rank, mixed_radix_unrank};
10use num_bigint::BigUint;
11
12/// Iterator over fixed-length words drawn from one alphabet.
13#[derive(Debug, Clone)]
14pub struct MixedRadixWords<'a, T> {
15    alphabet: &'a [T],
16    digits: Option<Vec<usize>>,
17    emitted: BigUint,
18    total: BigUint,
19}
20
21impl<'a, T> MixedRadixWords<'a, T> {
22    fn new(alphabet: &'a [T], length: usize) -> Self {
23        let total = word_count(alphabet.len(), length);
24        let digits = if length == 0 {
25            Some(Vec::new())
26        } else if alphabet.is_empty() {
27            None
28        } else {
29            Some(vec![0; length])
30        };
31        Self {
32            alphabet,
33            digits,
34            emitted: BigUint::from(0u32),
35            total,
36        }
37    }
38
39    /// Total number of words in this finite iterator.
40    pub fn total_ordinals(&self) -> &BigUint {
41        &self.total
42    }
43
44    /// Number of words not yet emitted.
45    pub fn remaining_ordinals(&self) -> BigUint {
46        if self.emitted >= self.total {
47            BigUint::from(0u32)
48        } else {
49            &self.total - &self.emitted
50        }
51    }
52}
53
54impl<T: Clone> Iterator for MixedRadixWords<'_, T> {
55    type Item = Vec<T>;
56
57    fn next(&mut self) -> Option<Self::Item> {
58        let digits = self.digits.as_ref()?.clone();
59        let word = digits
60            .iter()
61            .map(|&digit| self.alphabet[digit].clone())
62            .collect();
63        self.emitted += 1u32;
64
65        let mut next_digits = digits;
66        self.digits = if advance_digits(&mut next_digits, self.alphabet.len()) {
67            Some(next_digits)
68        } else {
69            None
70        };
71        Some(word)
72    }
73}
74
75/// Construct a lazy iterator over all fixed-length words from `alphabet`.
76///
77/// # Examples
78///
79/// ```
80/// use sim_lib_discrete_comb::words;
81///
82/// let alphabet = ["A", "B"];
83/// let generated: Vec<_> = words(&alphabet, 2).collect();
84/// assert_eq!(
85///     generated,
86///     vec![vec!["A", "A"], vec!["A", "B"], vec!["B", "A"], vec!["B", "B"]]
87/// );
88/// ```
89pub fn words<T: Clone>(alphabet: &[T], length: usize) -> MixedRadixWords<'_, T> {
90    MixedRadixWords::new(alphabet, length)
91}
92
93/// Exact fixed-alphabet word count, `alphabet_len.pow(length)`.
94pub fn word_count(alphabet_len: usize, length: usize) -> BigUint {
95    if length == 0 {
96        return BigUint::from(1u32);
97    }
98    if alphabet_len == 0 {
99        return BigUint::from(0u32);
100    }
101    let radix = BigUint::from(alphabet_len);
102    let mut total = BigUint::from(1u32);
103    for _ in 0..length {
104        total *= &radix;
105    }
106    total
107}
108
109/// Build the repeated mixed-radix vector for words over an alphabet.
110pub fn word_radices(alphabet_len: usize, length: usize) -> Result<Vec<u64>, CombError> {
111    if length == 0 {
112        return Ok(Vec::new());
113    }
114    if alphabet_len == 0 {
115        return Err(CombError::InvalidParameters(
116            "word radices require a non-empty alphabet for non-empty words".to_string(),
117        ));
118    }
119    let radix = u64::try_from(alphabet_len).map_err(|_| {
120        CombError::LimitExceeded(format!("alphabet length {alphabet_len} exceeds u64"))
121    })?;
122    Ok(vec![radix; length])
123}
124
125/// Convert mixed-radix digits into a word over `alphabet`.
126pub fn digits_to_word<T: Clone>(alphabet: &[T], digits: &[u64]) -> Result<Vec<T>, CombError> {
127    digits
128        .iter()
129        .map(|&digit| {
130            let index = usize::try_from(digit).map_err(|_| CombError::OutOfRange {
131                value: digit.to_string(),
132                bound: alphabet.len().to_string(),
133            })?;
134            alphabet.get(index).cloned().ok_or(CombError::OutOfRange {
135                value: digit.to_string(),
136                bound: alphabet.len().to_string(),
137            })
138        })
139        .collect()
140}
141
142/// Convert a word into mixed-radix digits over a unique `alphabet`.
143pub fn word_to_digits<T: Eq>(alphabet: &[T], word: &[T]) -> Result<Vec<u64>, CombError> {
144    reject_duplicate_alphabet(alphabet)?;
145    word.iter()
146        .map(|item| {
147            alphabet
148                .iter()
149                .position(|candidate| candidate == item)
150                .map(|index| {
151                    u64::try_from(index).map_err(|_| {
152                        CombError::LimitExceeded(format!("word index {index} exceeds u64"))
153                    })
154                })
155                .transpose()?
156                .ok_or_else(|| CombError::InvalidParameters("word item is not in alphabet".into()))
157        })
158        .collect()
159}
160
161/// Rank a word using the fixed-alphabet mixed-radix order.
162pub fn word_rank<T: Eq>(alphabet: &[T], word: &[T]) -> Result<BigUint, CombError> {
163    let digits = word_to_digits(alphabet, word)?;
164    let radices = word_radices(alphabet.len(), word.len())?;
165    mixed_radix_rank(&digits, &radices)
166}
167
168/// Unrank a fixed-length word from the fixed-alphabet mixed-radix order.
169pub fn word_unrank<T: Clone>(
170    alphabet: &[T],
171    length: usize,
172    rank: &BigUint,
173) -> Result<Vec<T>, CombError> {
174    let total = word_count(alphabet.len(), length);
175    if rank >= &total {
176        return Err(CombError::OutOfRange {
177            value: rank.to_string(),
178            bound: total.to_string(),
179        });
180    }
181    let radices = word_radices(alphabet.len(), length)?;
182    let digits = mixed_radix_unrank(rank, &radices)?;
183    digits_to_word(alphabet, &digits)
184}
185
186/// Return every unique cyclic rotation in canonical sorted order.
187///
188/// The first returned word is the canonical representative for the rotation
189/// class.
190pub fn canonical_cycles<T: Ord + Clone>(word: &[T]) -> Vec<Vec<T>> {
191    if word.is_empty() {
192        return vec![Vec::new()];
193    }
194    let mut rotations = (0..word.len())
195        .map(|start| {
196            word[start..]
197                .iter()
198                .chain(&word[..start])
199                .cloned()
200                .collect::<Vec<_>>()
201        })
202        .collect::<Vec<_>>();
203    rotations.sort();
204    rotations.dedup();
205    rotations
206}
207
208/// Keep only the items whose measured length is maximal.
209pub fn longest_only<T>(items: impl IntoIterator<Item = T>, len: impl Fn(&T) -> usize) -> Vec<T> {
210    let mut longest = Vec::new();
211    let mut best = None;
212    for item in items {
213        let item_len = len(&item);
214        match best {
215            None => {
216                best = Some(item_len);
217                longest.push(item);
218            }
219            Some(current) if item_len > current => {
220                best = Some(item_len);
221                longest.clear();
222                longest.push(item);
223            }
224            Some(current) if item_len == current => longest.push(item),
225            Some(_) => {}
226        }
227    }
228    longest
229}
230
231fn advance_digits(digits: &mut [usize], radix: usize) -> bool {
232    for index in (0..digits.len()).rev() {
233        digits[index] += 1;
234        if digits[index] < radix {
235            return true;
236        }
237        digits[index] = 0;
238    }
239    false
240}
241
242fn reject_duplicate_alphabet<T: Eq>(alphabet: &[T]) -> Result<(), CombError> {
243    for left in 0..alphabet.len() {
244        for right in (left + 1)..alphabet.len() {
245            if alphabet[left] == alphabet[right] {
246                return Err(CombError::InvalidParameters(
247                    "alphabet contains duplicate values".to_string(),
248                ));
249            }
250        }
251    }
252    Ok(())
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258    use std::sync::{
259        Arc,
260        atomic::{AtomicUsize, Ordering},
261    };
262
263    #[derive(Debug)]
264    struct CountedClone {
265        value: u8,
266        clones: Arc<AtomicUsize>,
267    }
268
269    impl Clone for CountedClone {
270        fn clone(&self) -> Self {
271            self.clones.fetch_add(1, Ordering::SeqCst);
272            Self {
273                value: self.value,
274                clones: Arc::clone(&self.clones),
275            }
276        }
277    }
278
279    #[test]
280    fn words_are_lazy_and_lexicographic() {
281        let clones = Arc::new(AtomicUsize::new(0));
282        let alphabet = [
283            CountedClone {
284                value: 0,
285                clones: Arc::clone(&clones),
286            },
287            CountedClone {
288                value: 1,
289                clones: Arc::clone(&clones),
290            },
291        ];
292
293        let first: Vec<_> = words(&alphabet, 8).take(3).collect();
294        assert_eq!(
295            first
296                .iter()
297                .map(|word| word.iter().map(|item| item.value).collect::<Vec<_>>())
298                .collect::<Vec<_>>(),
299            vec![
300                vec![0, 0, 0, 0, 0, 0, 0, 0],
301                vec![0, 0, 0, 0, 0, 0, 0, 1],
302                vec![0, 0, 0, 0, 0, 0, 1, 0],
303            ]
304        );
305        assert_eq!(clones.load(Ordering::SeqCst), 24);
306    }
307
308    #[test]
309    fn exact_count_handles_large_spaces() {
310        assert_eq!(word_count(3, 5), BigUint::from(243u32));
311        assert_eq!(word_count(2, 130), BigUint::from(1u32) << 130usize);
312        assert_eq!(words::<u8>(&[], 0).count(), 1);
313        assert_eq!(words::<u8>(&[], 3).count(), 0);
314    }
315
316    #[test]
317    fn word_digits_rank_and_unrank_round_trip() {
318        let alphabet = ["A", "B", "C"];
319        for (ordinal, word) in words(&alphabet, 3).enumerate() {
320            let rank = word_rank(&alphabet, &word).unwrap();
321            assert_eq!(rank, BigUint::from(ordinal as u32));
322            assert_eq!(word_unrank(&alphabet, 3, &rank).unwrap(), word);
323        }
324        assert_eq!(
325            digits_to_word(&alphabet, &[2, 0, 1]).unwrap(),
326            vec!["C", "A", "B"]
327        );
328        assert_eq!(
329            word_to_digits(&alphabet, &["C", "A", "B"]).unwrap(),
330            vec![2, 0, 1]
331        );
332    }
333
334    #[test]
335    fn adapters_reject_invalid_word_domains() {
336        assert!(matches!(
337            word_rank(&["A", "A"], &["A"]),
338            Err(CombError::InvalidParameters(_))
339        ));
340        assert!(matches!(
341            word_rank(&["A"], &["B"]),
342            Err(CombError::InvalidParameters(_))
343        ));
344        assert!(matches!(
345            word_unrank::<&str>(&[], 2, &BigUint::from(0u32)),
346            Err(CombError::OutOfRange { .. })
347        ));
348    }
349
350    #[test]
351    fn cycles_are_unique_and_canonical() {
352        assert_eq!(canonical_cycles::<u8>(&[]), vec![Vec::<u8>::new()]);
353        assert_eq!(
354            canonical_cycles(&[2, 1, 2, 1]),
355            vec![vec![1, 2, 1, 2], vec![2, 1, 2, 1]]
356        );
357        assert_eq!(
358            canonical_cycles(&[3, 1, 2]),
359            vec![vec![1, 2, 3], vec![2, 3, 1], vec![3, 1, 2]]
360        );
361    }
362
363    #[test]
364    fn longest_only_keeps_ties_without_materializing_losers() {
365        let longest = longest_only(vec!["a", "abcd", "xy", "wxyz"], |item| item.len());
366        assert_eq!(longest, vec!["abcd", "wxyz"]);
367    }
368}
sim_lib_discrete_comb/word.rs

sim_lib_discrete_comb/
word.rs
