ecgen/
gray_code.rs

1//! Gray code generation
2//!
3//! This module provides functionality for generating Gray codes, which are
4//! binary number systems where consecutive values differ by only one bit.
5//!
6//! ## Key Functions
7//!
8//! - [`brgc_gen`] - Generate binary reflected Gray code sequence
9//!
10//! ## Algorithm
11//!
12//! The binary reflected Gray code (BRGC) is generated recursively. For n bits,
13//! the sequence is generated by: 1) recursively generating the (n-1)-bit sequence,
14//! 2) adding the highest-order bit (0) to those, 3) adding the highest-order bit (1)
15//! to the reversed (n-1)-bit sequence.
16//!
17//! This produces a sequence of 2^n code words where each successive word differs
18//! by exactly one bit.
19//!
20//! ## Reference
21//!
22//! Gray codes were originally designed by Frank Gray (1953) for pulse code modulation.
23//!
24//! ## Complexity
25//!
26//! - `brgc_gen(n)`: O(2^n) output size, O(n) stack space
27//!
28#![cfg_attr(feature = "doc-images", doc = svgbobdoc::transform!(
29/// ```svgbob
30///   .───.    .───.    .───.    .───.
31///   │000│────│001│────│011│────│010│
32///   '───'    '───'    '───'    '───'
33///     │                  │
34///   .───.    .───.    .───.    .───.
35///   │100│────│101│    │111│────│110│
36///   '───'    '───'    '───'    '───'
37/// ```
38))]
39//!
40use genawaiter::sync::{Gen, GenBoxed};
41
42/// The `brgc_gen` function generates a binary reflexed gray code sequence of length `n`.
43///
44/// Binary reflected Gray code (BRGC) for $n$ bits:
45///
46/// $$ G(n) = 0 \cdot G(n-1) \oplus 1 \cdot G(n-1)^R $$
47///
48/// where $G(n-1)^R$ is the reverse of the $(n-1)$-bit sequence.
49///
50/// Arguments:
51///
52/// * `n`: The parameter `n` represents the number of bits in the binary reflexed gray code sequence.
53///
54/// Returns:
55///
56/// The function `brgc_gen` returns a `GenBoxed<usize>`, which is a boxed generator that yields values
57/// of type `usize`.
58///
59/// # Examples
60///
61/// ```
62/// use ecgen::brgc_gen;
63///
64/// let mut lst = ["⬜"; 3];
65/// println!("{}", lst.concat());
66/// let mut cnt = 1;
67/// for n in brgc_gen(lst.len()) {
68///     lst[n] = if lst[n] == "⬜" { "⬛" } else { "⬜" };
69///     println!("{}", lst.concat());
70///     cnt += 1;
71/// }
72///
73/// assert_eq!(cnt, 8);
74/// ```
75pub fn brgc_gen(n: usize) -> GenBoxed<usize> {
76    Gen::new_boxed(|co| async move {
77        if n < 1 {
78            return;
79        }
80        for i in brgc_gen(n - 1) {
81            co.yield_(i).await;
82        }
83        co.yield_(n - 1).await;
84        for i in brgc_gen(n - 1) {
85            co.yield_(i).await;
86        }
87    })
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_brgc() {
96        let mut cnt = 1;
97        for _n in brgc_gen(3) {
98            cnt += 1;
99        }
100        assert_eq!(cnt, 8);
101    }
102}
ecgen/gray_code.rs

ecgen/
gray_code.rs
