ecgen/combin.rs
1use genawaiter::sync::{Gen, GenBoxed};
2
3/// The `comb` function calculates the number of combinations of `k` elements from a set of `n`
4/// elements.
5///
6/// Arguments:
7///
8/// * `n`: The parameter `n` represents the total number of items or elements available for selection.
9/// * `k`: The parameter `k` represents the number of elements chosen from a set. It is used to
10/// calculate the number of combinations.
11///
12/// Returns:
13///
14/// The function `comb` returns the number of combinations of `k` elements that can be selected from a
15/// set of `n` elements.
16/// Number of combinations.
17///
18/// # Examples
19///
20/// ```
21/// use ecgen::comb;
22///
23/// assert_eq!(comb(3, 2), 3);
24/// assert_eq!(comb(6, 4), comb(6, 2));
25/// ```
26pub const fn comb(n: usize, k: usize) -> usize {
27 if k >= n || k == 0 {
28 1
29 } else {
30 comb_recur(n, k)
31 }
32}
33
34/// The `comb` function calculates the number of combinations of `k` elements from a set of `n`
35/// elements.
36///
37/// Arguments:
38///
39/// * `n`: The parameter `n` represents the total number of items or elements available for selection.
40/// * `k`: The parameter `k` represents the number of elements chosen from a set. It is used to
41/// calculate the number of combinations.
42///
43/// Returns:
44///
45/// The function `comb` returns the number of combinations of `k` elements that can be selected from a
46/// set of `n` elements.
47/// Number of combinations.
48#[inline]
49const fn comb_recur(n: usize, k: usize) -> usize {
50 let n = n - 1;
51 let a = if k == 1 { 1 } else { comb_recur(n, k - 1) };
52 let b = if k == n { 1 } else { comb_recur(n, k) };
53 a + b
54}
55
56/// Generate all combinations by homogeneous revolving-door
57///
58/// The `emk_comb_gen` function generates all combinations by using a homogeneous revolving-door algorithm.
59///
60/// Arguments:
61///
62/// * `n`: The parameter `n` represents the total number of elements in the combination set. It
63/// determines the range of indices that can be used in the combinations.
64/// * `k`: The parameter `k` represents the number of elements that will be swapped in each combination.
65///
66/// Returns:
67///
68/// The function `emk_gen` returns a `GenBoxed<(usize, usize)>`, which is a boxed generator that yields
69/// tuples of two `usize` values.
70///
71/// # Examples
72///
73/// ```
74/// use ecgen::emk_comb_gen;
75///
76/// let mut combin = [1, 1, 0];
77/// println!("{:?}", combin);
78/// let mut cnt = 1;
79/// for (i, j) in emk_comb_gen(3, 2) {
80/// combin.swap(i, j);
81/// println!("{:?}", combin);
82/// cnt += 1;
83/// }
84///
85/// assert_eq!(cnt, 3);
86/// ```
87pub fn emk_comb_gen(n: usize, k: usize) -> GenBoxed<(usize, usize)> {
88 Gen::new_boxed(|co| async move {
89 if n <= k || k == 0 {
90 return;
91 }
92 if k == 1 {
93 for i in 0..(n - 1) {
94 co.yield_((i, i + 1)).await;
95 }
96 return;
97 }
98 if k % 2 == 0 {
99 for (i, j) in emk_gen_even(n, k) {
100 co.yield_((i, j)).await;
101 }
102 } else {
103 for (i, j) in emk_gen_odd(n, k) {
104 co.yield_((i, j)).await;
105 }
106 }
107 })
108}
109
110/// Generate all combinations by homogeneous revolving-door
111///
112/// The `emk_comb_gen` function generates all combinations by using a homogeneous revolving-door algorithm.
113///
114/// Arguments:
115///
116/// * `n`: The parameter `n` represents the total number of elements in the combination set. It
117/// determines the range of indices that can be used in the combinations.
118/// * `k`: The parameter `k` represents the number of elements that will be swapped in each combination.
119///
120/// Returns:
121///
122/// The function `emk_gen` returns a `GenBoxed<(usize, usize)>`, which is a boxed generator that yields
123/// tuples of two `usize` values.
124///
125pub fn emk_gen_even(n: usize, k: usize) -> GenBoxed<(usize, usize)> {
126 Gen::new_boxed(|co| async move {
127 if k >= n - 1 {
128 co.yield_((n - 2, n - 1)).await;
129 } else {
130 for (i, j) in emk_gen_even(n - 1, k) {
131 co.yield_((i, j)).await;
132 }
133 co.yield_((n - 2, n - 1)).await;
134 if k == 2 {
135 for i in (0..(n - 3)).rev() {
136 co.yield_((i + 1, i)).await;
137 }
138 } else {
139 for (i, j) in emk_neg_odd(n - 2, k - 1) {
140 co.yield_((i, j)).await;
141 }
142 }
143 }
144 co.yield_((k - 2, n - 2)).await;
145
146 if k != 2 {
147 for (i, j) in emk_gen_even(n - 2, k - 2) {
148 co.yield_((i, j)).await;
149 }
150 }
151 })
152}
153
154/// Generate all combinations by homogeneous revolving-door
155///
156/// The `emk_comb_gen` function generates all combinations by using a homogeneous revolving-door algorithm.
157///
158/// Arguments:
159///
160/// * `n`: The parameter `n` represents the total number of elements in the combination set. It
161/// determines the range of indices that can be used in the combinations.
162/// * `k`: The parameter `k` represents the number of elements that will be swapped in each combination.
163///
164/// Returns:
165///
166/// The function `emk_gen` returns a `GenBoxed<(usize, usize)>`, which is a boxed generator that yields
167/// tuples of two `usize` values.
168///
169pub fn emk_gen_odd(n: usize, k: usize) -> GenBoxed<(usize, usize)> {
170 Gen::new_boxed(|co| async move {
171 if k < n - 1 {
172 for (i, j) in emk_gen_odd(n - 1, k) {
173 co.yield_((i, j)).await;
174 }
175 co.yield_((n - 2, n - 1)).await;
176 for (i, j) in emk_neg_even(n - 2, k - 1) {
177 co.yield_((i, j)).await;
178 }
179 } else {
180 co.yield_((n - 2, n - 1)).await;
181 }
182 co.yield_((k - 2, n - 2)).await;
183
184 if k == 3 {
185 for i in 0..(n - 3) {
186 co.yield_((i, i + 1)).await;
187 }
188 } else {
189 for (i, j) in emk_gen_odd(n - 2, k - 2) {
190 co.yield_((i, j)).await;
191 }
192 }
193 })
194}
195
196/// Generate all combinations by homogeneous revolving-door
197///
198/// The function `emk_neg` generates all combinations by using a homogeneous revolving-door algorithm.
199///
200/// Arguments:
201///
202/// * `n`: The parameter `n` represents the total number of elements in the set from which combinations
203/// are generated.
204/// * `k`: The parameter `k` represents the number of elements in each combination.
205///
206/// Returns:
207///
208/// The function `emk_neg` returns a generator that yields all combinations by homogeneous
209/// revolving-door. The combinations are represented as tuples of two usize values.
210fn emk_neg_even(n: usize, k: usize) -> GenBoxed<(usize, usize)> {
211 Gen::new_boxed(|co| async move {
212 if k != 2 {
213 for (i, j) in emk_neg_even(n - 2, k - 2) {
214 co.yield_((i, j)).await;
215 }
216 }
217 co.yield_((n - 2, k - 2)).await;
218 if k < n - 1 {
219 if k != 2 {
220 for (i, j) in emk_gen_odd(n - 2, k - 1) {
221 co.yield_((i, j)).await;
222 }
223 } else {
224 for i in 0..(n - 3) {
225 co.yield_((i, i + 1)).await;
226 }
227 }
228 co.yield_((n - 1, n - 2)).await;
229 for (i, j) in emk_neg_even(n - 1, k) {
230 co.yield_((i, j)).await;
231 }
232 } else {
233 co.yield_((n - 1, n - 2)).await;
234 }
235 })
236}
237
238/// Generate all combinations by homogeneous revolving-door
239///
240/// The function `emk_neg` generates all combinations by using a homogeneous revolving-door algorithm.
241///
242/// Arguments:
243///
244/// * `n`: The parameter `n` represents the total number of elements in the set from which combinations
245/// are generated.
246/// * `k`: The parameter `k` represents the number of elements in each combination.
247///
248/// Returns:
249///
250/// The function `emk_neg` returns a generator that yields all combinations by homogeneous
251/// revolving-door. The combinations are represented as tuples of two usize values.
252fn emk_neg_odd(n: usize, k: usize) -> GenBoxed<(usize, usize)> {
253 Gen::new_boxed(|co| async move {
254 if k == 3 {
255 for i in (0..(n - 3)).rev() {
256 co.yield_((i + 1, i)).await;
257 }
258 } else {
259 for (i, j) in emk_neg_odd(n - 2, k - 2) {
260 co.yield_((i, j)).await;
261 }
262 }
263 co.yield_((n - 2, k - 2)).await;
264 if k >= n - 1 {
265 co.yield_((n - 1, n - 2)).await;
266 } else {
267 for (i, j) in emk_gen_even(n - 2, k - 1) {
268 co.yield_((i, j)).await;
269 }
270 co.yield_((n - 1, n - 2)).await;
271 for (i, j) in emk_neg_odd(n - 1, k) {
272 co.yield_((i, j)).await;
273 }
274 }
275 })
276}
277
278#[cfg(test)]
279mod tests {
280 use super::*;
281
282 #[test]
283 fn comb_test() {
284 assert_eq!(comb(3, 2), 3);
285 assert_eq!(comb(6, 4), comb(6, 2));
286 assert_eq!(comb(6, 6), 1);
287 assert_eq!(comb(0, 0), 1);
288 assert_eq!(comb(0, 1), 1);
289 assert_eq!(comb(1, 1), 1);
290 assert_eq!(comb(1, 0), 1);
291 assert_eq!(comb(2, 2), 1);
292 assert_eq!(comb(2, 1), 2);
293 assert_eq!(comb(2, 0), 1);
294 assert_eq!(comb(3, 3), 1);
295 assert_eq!(comb(3, 2), 3);
296 }
297
298 #[test]
299 fn test_emk_even_odd() {
300 let mut cnt = 1;
301 for (_x, _y) in emk_comb_gen(16, 5) {
302 cnt += 1;
303 }
304 assert_eq!(cnt, comb(16, 5));
305 }
306
307 #[test]
308 fn test_emk_odd_odd() {
309 let mut cnt = 1;
310 for (_x, _y) in emk_comb_gen(15, 5) {
311 cnt += 1;
312 }
313 assert_eq!(cnt, comb(15, 5));
314 }
315
316 #[test]
317 fn test_emk_even_even() {
318 let mut cnt = 1;
319 for (_x, _y) in emk_comb_gen(16, 6) {
320 cnt += 1;
321 }
322 assert_eq!(cnt, comb(16, 6));
323 }
324
325 #[test]
326 fn test_emk_odd_even() {
327 let mut cnt = 1;
328 for (_x, _y) in emk_comb_gen(15, 6) {
329 cnt += 1;
330 }
331 assert_eq!(cnt, comb(15, 6));
332 }
333}