ecgen/
perm.rs

1use genawaiter::sync::{Gen, GenBoxed};
2
3// /// For future rust version:
4// const fn factorial2<const N: usize>() -> usize {
5//     if N < 2 {
6//         1
7//     } else {
8//         const M: usize = N - 1;
9//         N * factorial2::<M>()
10//     }
11// }
12
13/// The `factorial` function calculates the factorial of a given number.
14///
15/// Arguments:
16///
17/// * `n`: The parameter `n` represents the number for which we want to calculate the factorial.
18///
19/// Returns:
20///
21/// The `factorial` function returns the factorial of the input number `n`.
22///
23/// # Examples
24///
25/// ```
26/// use ecgen::factorial;
27///  
28/// assert_eq!(factorial(5), 120);
29/// assert_eq!(factorial(1), 1);
30/// ```
31pub const fn factorial(n: usize) -> usize {
32    if n < 2 {
33        1
34    } else {
35        n * factorial(n - 1)
36    }
37}
38
39/// Generate all permutations by adjacent transposition
40///
41/// The `sjt_gen` function in Rust generates all permutations of a given length using the
42/// Steinhaus-Johnson-Trotter algorithm.
43///
44/// Arguments:
45///
46/// * `n`: The parameter `n` represents the number of elements in the permutation.
47///
48/// Returns:
49///
50/// The function `sjt_gen` returns a boxed generator that yields permutations of indices.
51///
52/// # Examples
53///
54/// ```
55/// use ecgen::sjt_gen;
56///  
57/// let mut perm = ["🍉", "🍌", "🍇", "🍏"];
58/// let mut cnt = 0;
59/// for n in sjt_gen(perm.len()) {
60///     println!("{}", perm.concat());
61///     cnt += 1;
62///     perm.swap(n, n + 1);
63/// }
64///
65/// assert_eq!(cnt, 24);
66/// assert_eq!(perm, ["🍉", "🍌", "🍇", "🍏"]); // Hamilton cycle
67/// ```
68pub fn sjt_gen(n: usize) -> GenBoxed<usize> {
69    Gen::new_boxed(|co| {
70        async move {
71            /* Generate the swaps for the Steinhaus-Johnson-Trotter algorithm. */
72            if n == 2 {
73                co.yield_(0).await;
74                co.yield_(0).await; // tricky part: return to the original list
75                return;
76            }
77            let mut even = true;
78            for j in sjt_gen(n - 1) {
79                if even {
80                    // downward
81                    for i in (0..n - 1).rev() {
82                        co.yield_(i).await;
83                    }
84                    co.yield_(1 + j).await;
85                    even = false;
86                } else {
87                    // upward
88                    for i in 0..n - 1 {
89                        co.yield_(i).await;
90                    }
91                    co.yield_(j).await;
92                    even = true;
93                }
94            }
95        }
96    })
97}
98
99/// Generate all permutations by star transposition
100///
101/// The `ehr_gen` function generates all permutations of a given length using the star transposition
102/// algorithm.
103///
104/// Arguments:
105///
106/// * `n`: The parameter `n` represents the number of elements in the permutation. In the given example,
107///        `n` is set to 4, so it generates permutations of 4 elements.
108///
109/// Returns:
110///
111/// The function `ehr_gen` returns a `GenBoxed<usize>`, which is a boxed generator that yields `usize`
112/// values.
113///
114/// # Examples
115///
116/// ```
117/// use ecgen::ehr_gen;
118///  
119/// let mut perm = ["🍉", "🍌", "🍇", "🍏"];
120/// let mut cnt = 1;
121/// println!("{}", perm.concat());
122/// for n in ehr_gen(perm.len()) {
123///     perm.swap(0, n);
124///     println!("{}", perm.concat());
125///     cnt += 1;
126/// }
127///
128/// assert_eq!(cnt, 24);
129/// assert_eq!(perm, ["🍏", "🍌", "🍇", "🍉"]);
130/// ```
131pub fn ehr_gen(n: usize) -> GenBoxed<usize> {
132    Gen::new_boxed(|co| {
133        async move {
134            let mut c = vec![0; n + 1]; // c[0] is never used
135            let mut b: Vec<usize> = (0..n).collect(); // 0, ... n-1
136            loop {
137                let mut k: usize = 1;
138                loop {
139                    if c[k] == k {
140                        c[k] = 0;
141                        k += 1;
142                    }
143                    if c[k] < k {
144                        break;
145                    }
146                }
147                if k == n {
148                    break;
149                }
150                c[k] += 1;
151                co.yield_(b[k]).await;
152                b[1..k].reverse();
153            }
154        }
155    })
156}
157
158#[cfg(test)]
159mod tests {
160    use super::*;
161
162    #[test]
163    fn test_sjt() {
164        let mut cnt = 0;
165        for _n in sjt_gen(4) {
166            cnt += 1;
167        }
168        assert_eq!(cnt, factorial(4));
169    }
170
171    #[test]
172    fn test_ehr() {
173        let mut cnt = 1;
174        for _n in ehr_gen(4) {
175            cnt += 1;
176        }
177        assert_eq!(cnt, factorial(4));
178    }
179}
ecgen/perm.rs

ecgen/
perm.rs
