ecgen/set_bipart.rs
1use genawaiter::sync::{Gen, GenBoxed};
2
3/// The `stirling2nd2` function calculates the Stirling number of the second kind specifically for k =
4/// 2.
5///
6/// Arguments:
7///
8/// * `n`: The parameter `n` represents the number of elements in a set. The `stirling2nd2` function
9/// calculates the Stirling number of the second kind specifically for `k = 2`, which represents the
10/// number of non-empty subsets that can be formed from a set of `n` elements
11///
12/// Returns:
13///
14/// The `stirling2nd2` function returns the Stirling number of the second kind specifically for k = 2.
15///
16/// # Examples
17///
18/// ```
19/// use ecgen::stirling2nd2;
20///
21/// assert_eq!(stirling2nd2(5), 15);
22/// ```
23#[inline]
24pub const fn stirling2nd2(n: usize) -> usize {
25 if n <= 2 {
26 1
27 } else {
28 1 + 2 * stirling2nd2(n - 1)
29 }
30}
31
32/// The `set_bipart_gen` function generates a sequence of numbers representing moves between two blocks.
33///
34/// Arguments:
35///
36/// * `n`: The parameter `n` represents the number of elements in the set that you want to bipart.
37///
38/// Returns:
39///
40/// The function `set_bipart_gen` returns a boxed generator of type `GenBoxed<usize>`.
41///
42/// # Examples
43///
44/// ```
45/// use ecgen::set_bipart_gen;
46///
47/// const N: usize = 5;
48///
49/// // 0 0 0 0 0 1
50/// let mut b = [0; N + 1];
51/// b[N] = 1; // b[0] is unused
52/// let mut cnt = 1;
53/// for x in set_bipart_gen(N) {
54/// let old = b[x];
55/// b[x] = 1 - b[x];
56/// println!("Move {} from Block {} to Block {}", x, old, b[x]);
57/// cnt += 1;
58/// }
59///
60/// assert_eq!(cnt, 15);
61/// ```
62pub fn set_bipart_gen(n: usize) -> GenBoxed<usize> {
63 Gen::new_boxed(|co| async move {
64 for i in gen0_even(n) {
65 co.yield_(i).await;
66 }
67 })
68}
69
70/// S(n,k,0) even k
71/// The function `gen0_even` generates a sequence of even numbers starting from `n` and yielding the
72/// previous number, followed by the even numbers from `gen1_even(n-1)` and the negative even numbers
73/// from `neg1_even(n-1)`.
74///
75/// Arguments:
76///
77/// * `n`: The parameter `n` represents the upper limit for generating even numbers. The function
78/// `gen0_even` generates a sequence of even numbers starting from `n` and going down to 2.
79///
80/// Returns:
81///
82/// The function `gen0_even` returns a boxed generator (`GenBoxed<usize>`).
83#[inline]
84fn gen0_even(n: usize) -> GenBoxed<usize> {
85 Gen::new_boxed(|co| async move {
86 if n < 3 {
87 return;
88 }
89 co.yield_(n - 1).await;
90 for i in gen1_even(n - 1) {
91 co.yield_(i).await;
92 } // S(n-1, k, 1).(k-1)
93 co.yield_(n).await;
94 for i in neg1_even(n - 1) {
95 co.yield_(i).await;
96 } // S'(n-1, k, 1).(k-2)
97 })
98}
99
100/// The function `gen1_even` generates a sequence of even numbers from 2 to n, where n is an input
101/// parameter.
102///
103/// Arguments:
104///
105/// * `n`: The parameter `n` represents the upper limit of the range of numbers to generate.
106///
107/// Returns:
108///
109/// The function `gen1_even` returns a boxed generator that yields even numbers from 2 to `n`,
110/// inclusive, in a specific pattern.
111/// S(n,k,1) even k
112#[inline]
113fn gen1_even(n: usize) -> GenBoxed<usize> {
114 Gen::new_boxed(|co| async move {
115 if n < 3 {
116 return;
117 }
118 co.yield_(2).await;
119 for i in neg1_even(n - 1) {
120 co.yield_(i).await;
121 }
122 co.yield_(n).await;
123 for i in gen1_even(n - 1) {
124 co.yield_(i).await;
125 }
126 })
127}
128
129/// S'(n,k,1) even k
130/// The function `neg1_even` generates a sequence of even numbers from 2 to n, where n is an input
131/// parameter.
132///
133/// Arguments:
134///
135/// * `n`: The parameter `n` represents the upper limit of the range of numbers to generate.
136///
137/// Returns:
138///
139/// The function `neg1_even` returns a boxed generator that yields even numbers from 2 to `n`,
140/// inclusive, in a specific pattern.
141/// S(n,k,1) even k
142#[inline]
143fn neg1_even(n: usize) -> GenBoxed<usize> {
144 Gen::new_boxed(|co| async move {
145 if n < 3 {
146 return;
147 }
148 for i in neg1_even(n - 1) {
149 co.yield_(i).await;
150 }
151 co.yield_(n).await;
152 for i in gen1_even(n - 1) {
153 co.yield_(i).await;
154 }
155 co.yield_(2).await;
156 })
157}
158
159#[cfg(test)]
160mod tests {
161 use super::*;
162
163 #[test]
164 fn test_set_bipart_odd() {
165 const N: usize = 11;
166
167 // 0 0 0 0 0 1
168 let mut b = [0; N + 1];
169 b[N] = 1; // b[0] is unused
170 let mut cnt = 1;
171 for x in set_bipart_gen(N) {
172 let old = b[x];
173 b[x] = 1 - b[x];
174 println!("Move {} from Block {} to Block {}", x, old, b[x]);
175 cnt += 1;
176 }
177 assert_eq!(cnt, stirling2nd2(N));
178 }
179
180 #[test]
181 fn test_set_bipart_even() {
182 const N: usize = 10;
183
184 // 0 0 0 0 0 1
185 let mut b = [0; N + 1];
186 b[N] = 1; // b[0] is unused
187 let mut cnt = 1;
188 for x in set_bipart_gen(N) {
189 let old = b[x];
190 b[x] = 1 - b[x];
191 println!("Move {} from Block {} to Block {}", x, old, b[x]);
192 cnt += 1;
193 }
194 assert_eq!(cnt, stirling2nd2(N));
195 }
196
197 /// The function `test_set_bipart_special` tests the correctness of the `set_bipart_gen` function by
198 /// comparing its output with the `stirling2nd2` function.
199 #[test]
200 fn test_set_bipart_special() {
201 const N: usize = 2;
202
203 let mut cnt = 1;
204 for _x in set_bipart_gen(N) {
205 cnt += 1;
206 }
207 assert_eq!(cnt, stirling2nd2(N));
208 }
209}