set_partitions/
lib.rs

1#![deny(missing_docs)]
2
3//! The **set-partition** crate provides ways to represent, enumerate and count
4//! all the possible partitions of a set of a given finite size into subsets.
5//!
6//! You can use the `set_partitions` function to get the number of partitions of a set
7//! with `n` elements, and you can use the `SetPartition` struct and its `increment`()
8//! function to enumerate them (as well as its more generic variants).
9//!
10//! Set partitions are represented as sequences of values, with one value for each
11//! element of the partitioned set, such that if two elements are in the same subset,
12//! the sequence will have the same values at the corresponding indices.
13//!
14//! Among all the possible sequences, the one which is lexicographically minimal,
15//! and uses values starting from Default::default() and incrementing with increment(),
16//! is chosen as the representative.
17//!
18//! See <http://www-cs-faculty.stanford.edu/~uno/fasc3b.ps.gz> page 27 for more information
19//! and a description of the algorithm used here.
20//!
21//! # How to use
22//!
23//! For fixed size set partitions, use `SetPartition#`; use `GenSetPartition#` if you want to use something other than `u8` as the data type.
24//! For variable size set partitions up to 16 elements (more than 16 result in more than 2^32 partitions), use `SmallSetPartition` or `GenSetPartition`, 
25//! For medium sized variable size set partitions, use `ArrayVecSetPartition`.
26//! For arbitrary sized set partitions, use `VecSetPartition`.
27//!
28//! If you don't care about getting the subset contents, pass `()` or omit the type parameter.
29//! Otherwise, use `SmallSubsets` or `GenSmallSubsets` to represent subsets using ArrayVecs without memory allocation, for set partitions of size 16 or less.
30//! For subsets in other data structures, you can use `ArrayVecSubsets`, `VecSubsets`,`HashSubsets` or `BTreeSubsets`.
31//!
32//! To enumerate set partitions, call `increment()` until it returns `false`, and use `get()`, `num_subsets()` or `subsets().subsets()` to examine the set partition.
33
34use arrayvec::ArrayVec;
35use std::fmt;
36use std::fmt::Debug;
37use std::cmp::{PartialOrd, Ord, PartialEq, Eq, Ordering};
38use std::hash::{Hash, Hasher};
39use std::collections::hash_set::HashSet;
40use std::collections::btree_set::BTreeSet;
41use std::ops;
42use std::ops::{Deref, Index};
43use std::slice;
44use std::borrow::Borrow;
45use std::collections::{btree_map, hash_map};
46
47/// Module for the Incrementable trait
48pub mod traits
49{
50    use num_traits::One;
51    use std::ops::{Add, AddAssign};
52
53    /// Trait for things that can be incremented, like numbers
54    pub trait Incrementable
55    {
56        /// Increment self by mutable reference
57        fn increment(&mut self);
58
59        /// Increment self and return it
60        fn incremented(mut self) -> Self 
61            where Self: Sized
62        {
63            self.increment();
64            self
65        }
66    }
67
68    impl<T> Incrementable for T
69        where T: One + Add<T, Output = T> + AddAssign<T>
70    {
71        fn increment(&mut self) {
72            *self += One::one();
73        }
74
75        fn incremented(self) -> T {
76            self + <T as One>::one()
77        }
78    }
79
80    /*
81    // this needs specialization to work...
82    impl<T> Incrementable for T
83        where T: Iterator
84    {
85        fn increment(&mut self) {
86            self.next();
87        }
88    }
89    */
90}
91use crate::traits::Incrementable;
92
93/// Trait used by `SetPartition` structs to notify the subsets structure of changes.
94///
95/// A no-op implementation is available for `()`.
96///
97/// The `VecSubsets`, `HashSubsets`, `BTreeSubsets` structs implement this
98/// trait to provide an updated view of the subsets in the partition, represented
99/// with `Vec`, `HashSet` or `BTreeSet` types respectively.
100pub trait Subsets<T> : Default
101{
102    /// Set the number of non-empty sets to `m` converted to usize
103    fn set_limit(&mut self, m: &T);
104
105    /// Increment the number of non-empty sets
106    fn inc_limit(&mut self);
107
108    /// Clear all sets, reset the number of non-empty sets to 0
109    fn clear(&mut self);
110
111    /// Truncate the number of sets to at most `n`
112    fn done(&mut self, n: usize);
113
114    /// Reset to the trivial partition of size `n`
115    fn reset(&mut self, n: usize);
116
117    /// Notify addition of `idx` to the set identified by `v`
118    ///
119    /// Items must be added to a set in their correct order.
120    fn add(&mut self, idx: usize, v: &T);
121
122    /// Notify removal of `idx` from the set identified by `v`
123    ///
124    /// This must be the last index added to that set.
125    fn remove(&mut self, idx: usize, v: &T);
126}
127
128impl<T> Subsets<T> for ()
129{
130    fn set_limit(&mut self, _: &T) {}
131    fn inc_limit(&mut self) {}
132    fn clear(&mut self) {}
133    fn done(&mut self, _: usize) {}
134    fn reset(&mut self, _: usize) {}
135    fn add(&mut self, _: usize, _: &T) {}
136    fn remove(&mut self, _: usize, _: &T) {}
137}
138
139macro_rules! impl_subsets_for_subsets {
140    ($T:ty) => {
141        fn set_limit(&mut self, m: &$T)
142        {
143            self.n = TryInto::try_into((*m).clone()).unwrap();
144        }
145
146        fn inc_limit(&mut self)
147        {
148            self.n += 1;
149        }
150
151        fn clear(&mut self)
152        {
153            for s in self.subsets.iter_mut() {
154                s.clear();
155            }
156            self.n = 0;
157        }
158
159        fn done(&mut self, n: usize)
160        {
161            self.truncate(n);
162        }
163    }
164}
165
166macro_rules! impl_traits_for_subsets {
167    ($S:ty, {$($impl:tt)*}, {$($where:tt)*}) => {
168        $($impl)* Default for $S
169            $($where)*
170        {
171            fn default() -> Self {
172                Self {
173                    subsets: Default::default(),
174                    n: 0
175                }
176            }
177        }
178    }
179}
180
181macro_rules! impl_set_subsets {
182    ($S:ty, $T:ty, {$($impl:tt)*}, {$($where:tt)*}) => {
183        $($impl)* Subsets<T> for $S
184            $($where)*
185        {
186            impl_subsets_for_subsets!($T);
187
188            fn reset(&mut self, n: usize)
189            {
190                self.done(n);
191
192                for s in self.subsets.iter_mut() {
193                    s.clear();
194                }
195
196                if self.subsets.is_empty() {
197                    self.subsets.push(Default::default());
198                }
199
200                if let Some(s0) = self.subsets.first_mut() {
201                    for i in 0..n {
202                        s0.insert(TryInto::try_into(i).unwrap());
203                    }
204                }
205                self.n = if n > 0 {1} else {0}
206            }
207
208            fn add(&mut self, idx: usize, v: &$T)
209            {
210                let vi: usize = TryInto::try_into((*v).clone()).unwrap();
211                self.enlarge(vi + 1);
212                let it: $T = TryInto::try_into(idx).unwrap();
213                self.subsets[vi].insert(it);
214            }
215
216            fn remove(&mut self, idx: usize, v: &$T)
217            {
218                let vi: usize = TryInto::try_into((*v).clone()).unwrap();
219                let it: $T = TryInto::try_into(idx).unwrap();
220                self.subsets[vi].remove(&it);
221            }
222        }
223
224        impl_traits_for_subsets!($S, {$($impl)*}, {$($where)*});
225    }
226}
227
228macro_rules! impl_vec_subsets {
229    ($S:ty, $T:ty, {$($impl:tt)*}, {$($where:tt)*}) => {
230        $($impl)* Subsets<$T> for $S
231            $($where)*
232        {
233            impl_subsets_for_subsets!($T);
234
235            fn reset(&mut self, n: usize)
236            {
237                self.done(n);
238
239                for s in self.subsets.iter_mut() {
240                    s.clear();
241                }
242
243                if self.subsets.is_empty() {
244                    self.subsets.push(Default::default());
245                }
246
247                if let Some(s0) = self.subsets.first_mut() {
248                    for i in 0..n {
249                        s0.push(TryInto::try_into(i).unwrap());
250                    }
251                }
252                self.n = if n > 0 {1} else {0}
253            }
254
255            fn add(&mut self, idx: usize, v: &$T)
256            {
257                let vi: usize = TryInto::try_into((*v).clone()).unwrap();
258                self.enlarge(vi + 1);
259                let it: $T = TryInto::try_into(idx).unwrap();
260                self.subsets[vi].push(it);
261            }
262
263            fn remove(&mut self, _: usize, v: &$T)
264            {
265                let vi: usize = TryInto::try_into((*v).clone()).unwrap();
266                self.subsets[vi].pop();
267                //debug_assert_eq!(r, Some(idx.into()));
268            }
269        }
270
271        impl_traits_for_subsets!($S, {$($impl)*}, {$($where)*});
272    }
273}
274
275macro_rules! impl_subsets_helpers {
276    () => {
277        fn truncate(&mut self, n: usize)
278        {
279            self.subsets.truncate(n);
280        }
281
282        fn enlarge(&mut self, new_n: usize)
283        {
284            let n = self.subsets.len();
285            if n < new_n {
286                self.subsets.reserve(new_n - n);
287                loop {
288                    self.subsets.push(Default::default());
289                    if self.subsets.len() == new_n {break;}
290                }
291            }
292        }
293    }
294}
295
296/// Maintains subsets of a set partition using `HashSet`s
297///
298/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
299#[derive(Clone, Debug)]
300pub struct HashSubsets<T>
301    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Hash + Eq
302{
303    subsets: Vec<HashSet<T>>,
304    n: usize
305}
306
307impl<T> HashSubsets<T>
308    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Hash + Eq
309{
310    /// Return the non-empty subsets part of the set partition
311    pub fn subsets(&self) -> &[HashSet<T>] {
312        &self.subsets[..self.n]
313    }
314
315    impl_subsets_helpers!();
316}
317
318impl_set_subsets!(HashSubsets<T>, T, {impl<T>}, {where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Hash + Eq});
319
320/// Maintains subsets of a set partition using `BTreeSet`s
321///
322/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
323#[derive(Clone, Debug)]
324pub struct BTreeSubsets<T>
325    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Ord
326{
327    subsets: Vec<BTreeSet<T>>,
328    n: usize
329}
330
331impl<T> BTreeSubsets<T>
332    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Ord
333{
334    /// Return the non-empty subsets part of the set partition
335    pub fn subsets(&self) -> &[BTreeSet<T>] {
336        &self.subsets[..self.n]
337    }
338
339    impl_subsets_helpers!();
340}
341
342impl_set_subsets!(BTreeSubsets<T>, T, {impl<T>}, {where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize> + Ord});
343
344/// Maintains subsets of a set partition using `Vec`s
345///
346/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
347#[derive(Clone, Debug)]
348pub struct VecSubsets<T>
349    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize>
350{
351    subsets: Vec<Vec<T>>,
352    n: usize
353}
354
355impl<T> VecSubsets<T>
356    where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize>
357{
358    /// Return the non-empty subsets part of the set partition
359    pub fn subsets(&self) -> &[Vec<T>] {
360        &self.subsets[..self.n]
361    }
362
363    impl_subsets_helpers!();
364}
365
366impl_vec_subsets!(VecSubsets<T>, T, {impl<T>}, {where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize>});
367
368
369/// Maintains subsets of a set partition using `ArrayVec`s
370///
371/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
372#[derive(Debug, Clone)]
373pub struct ArrayVecSubsets<T, const N: usize>
374{
375    subsets: ArrayVec<ArrayVec<T, N>, N>,
376    n: usize
377}
378
379impl<T, const N: usize> ArrayVecSubsets<T, N>
380{
381    /// Return the non-empty subsets part of the set partition
382    pub fn subsets(&self) -> &[ArrayVec<T, N>] {
383        &self.subsets[..self.n]
384    }
385
386    fn truncate(&mut self, n: usize)
387    {
388        while self.subsets.len() > n {
389            self.subsets.pop();
390        }
391    }
392
393    fn enlarge(&mut self, new_n: usize)
394    {
395        let n = self.subsets.len();
396        if n < new_n {
397            loop {
398                self.subsets.push(Default::default());
399                if self.subsets.len() == new_n {break;}
400            }
401        }
402    }
403}
404
405impl_vec_subsets!(ArrayVecSubsets<T, N>, T, {impl<T, const N: usize>}, {where <T as TryInto<usize>>::Error : Debug, <T as TryFrom<usize>>::Error : Debug, T: Clone + TryInto<usize> + TryFrom<usize>});
406
407/// Maintains subsets of a set partition using 16-entry `ArrayVec`s
408///
409/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
410pub type GenSmallSubsets<T> = ArrayVecSubsets<T, 16>;
411
412/// Maintains subsets of a set partition using 16-entry `ArrayVec`s
413///
414/// Pass this as the `Subsets` implementation to the `SetPartition` structs.
415pub type SmallSubsets = GenSmallSubsets<u8>;
416
417trait Push
418{
419    type Item;
420
421    fn try_push(&mut self, x: Self::Item) -> Result<(), ()>;
422    fn done(&mut self) -> Result<(), ()>;
423}
424
425struct SlicePusher<'a, T: 'a>
426{
427    iter: std::slice::IterMut<'a, T>
428}
429
430impl<'a, T: 'a> SlicePusher<'a, T>
431{
432    pub fn new(s: &'a mut [T]) -> Self
433    {
434        SlicePusher {iter: s.iter_mut()}
435    }
436}
437
438impl<'a, T> Push for SlicePusher<'a, T>
439{
440    type Item = T;
441
442    fn try_push(&mut self, x: Self::Item) -> Result<(), ()>
443    {
444        if let Some(a) = self.iter.next() {
445            *a = x;
446            Ok(())
447        } else {
448            Err(())
449        }
450    }
451
452    fn done(&mut self) -> Result<(), ()>
453    {
454        if self.iter.next().is_none() {
455            Ok(())
456        } else {
457            Err(())
458        }
459    }
460}
461
462impl<T> Push for Vec<T>
463{
464    type Item = T;
465
466    fn try_push(&mut self, x: Self::Item) -> Result<(), ()>
467    {
468        self.push(x);
469        Ok(())
470    }
471
472    fn done(&mut self) -> Result<(), ()>
473    {
474        Ok(())
475    }
476}
477
478impl<T, const N: usize> Push for ArrayVec<T, N>
479{
480    type Item = T;
481
482    fn try_push(&mut self, x: Self::Item) -> Result<(), ()>
483    {
484        self.try_push(x).map_err(|_| ())
485    }
486
487    fn done(&mut self) -> Result<(), ()>
488    {
489        Ok(())
490    }
491}
492
493macro_rules! do_try_set {
494    ($T:ty, $self:expr, $s:expr, $map:expr, $map_mod:tt) => {
495        {
496            let this = $self;
497            let mut s = $s;
498            let mut map = $map;
499            let mut old_m = <$T>::default();
500            let mut m = <$T>::default().incremented();
501
502            {
503                let mut i = 0;
504                #[allow(unused_mut)]
505                let (mut a, mut b, h) = this.pushers();
506                {
507                    if let Some(ai) = s.next() {
508                        map.insert(ai, <$T>::default());
509                        let v = <$T>::default();
510                        h.add(i, &v);
511                        i += 1;
512                        a.try_push(v).map_err(|_| ())?;
513                    }
514                }
515
516                for si in s {
517                    if old_m == <$T>::default() {
518                        old_m.increment();
519                    }
520                    b.try_push(old_m).map_err(|_| ())?;
521                    old_m = m.clone();
522
523                    let ai = match map.entry(si) {
524                        $map_mod::Entry::Occupied(e) => e.get().clone(),
525                        $map_mod::Entry::Vacant(e) => {
526                            let ai = m.clone();
527                            e.insert(ai.clone());
528                            m.increment();
529                            ai
530                        }
531                    };
532                    h.add(i, &ai);
533                    i += 1;
534                    a.try_push(ai).map_err(|_| ())?;
535                }
536                
537                a.done()?;
538                b.done()?;
539                h.done(i);
540                if i != 0 {
541                    h.set_limit(&m);
542                }
543            }
544            this.m = old_m;
545
546            Ok(map)
547        }
548    }
549}
550
551macro_rules! impl_set_partition {
552    ($SP:ty, $T:ty, {$($impl:tt)*}, {$($impl_a:tt)*}, {$($where:tt)*}) => {
553        $($impl)* $SP
554            $($where)* {
555            /// Returns a reference to the sequence representing the partition
556            pub fn get(&self) -> &[$T] {
557                &self.a
558            }
559
560            /// Returns the size of the set being partitioned
561            pub fn len(&self) -> usize {
562                self.a.len()
563            }
564
565            /// Reset to the trivial set partition of size `self`.`len`()
566            pub fn reset(&mut self) {
567                self.do_reset();
568                self.h.reset(self.a.len());
569            }
570
571            fn do_reset(&mut self) {
572                let n = self.len() as usize;
573                for i in self.a.iter_mut() {
574                    *i = <$T>::default();
575                }
576                for i in self.b.iter_mut() {
577                    *i = <$T>::default().incremented();
578                }
579                if n > 1 {
580                    self.m = <$T>::default().incremented();
581                } else {
582                    self.m = <$T>::default();
583                }
584            }
585
586            /// Move to the next set partition in lexicographic order of sequences,
587            /// returning `true`, or to the first trivial partition, returning `false`.
588            #[inline]
589            pub fn increment(&mut self) -> bool {
590                // algorithm from TAoCP 3b page 27
591                let n = self.a.len();
592                if let Some(al) = self.a.last_mut() {
593                    if *al != self.m {
594                        self.h.remove(n - 1, al);
595                        al.increment();
596                        self.h.add(n - 1, al);
597                        if *al == self.m {
598                            self.h.inc_limit();
599                        }
600                        return true;
601                    }
602                } else {
603                    return false;
604                }
605
606                self.increment_slowpath()
607            }
608
609            fn increment_slowpath(&mut self) -> bool {
610                let n = self.len();
611                if n <= 1 {
612                    return false;
613                }
614
615                let mut j = n - 2;
616                while self.a[j] == self.b[j] {
617                    j = j - 1;
618                }
619                if j == 0 {
620                    self.reset();
621                    return false;
622                }
623
624                for k in ((j + 1)..n).rev() {
625                    let ak = &mut self.a[k];
626                    self.h.remove(k, ak);
627                }
628
629                let m = {
630                    let aj = &mut self.a[j];
631                    self.h.remove(j, aj);
632                    aj.increment();
633                    self.h.add(j, aj);
634                    let bj = self.b[j].clone();
635                    if *aj == bj {bj.incremented()} else {bj}
636                };
637                j += 1;
638
639                for k in j..n {
640                    let ak = &mut self.a[k];
641                    *ak = <$T>::default();
642                    self.h.add(k, ak);
643                }
644                for bi in &mut self.b[j..] {
645                    *bi = m.clone();
646                }
647                self.m = m;
648                self.h.set_limit(&self.m);
649                true
650            }
651        
652            /// Create a set partition from an iterator of `Hash`-implementing elements.
653            ///
654            /// Returns the set partition and a map from iterator elements to representative values.
655            ///
656            /// Use `try_from_ord` instead if `Hash` is not implemented on the iterator elements.
657            pub fn try_from<S>(s: S) -> Result<($SP, hash_map::HashMap<<S as Iterator>::Item, $T>), ()>
658                where S: Iterator, <S as Iterator>::Item : Hash + Eq
659            {
660                let mut sp = <$SP>::new();
661                sp.try_set(s).map(|map| (sp, map))
662            }
663
664            /// Sets a set partition from an iterator of `Hash`-implementing elements.
665            ///
666            /// Returns a map from iterator elements to representative values.
667            ///
668            /// Use `try_set_ord` instead if `Hash` is not implemented on the iterator elements.
669            pub fn try_set<S>(&mut self, s: S) -> Result<hash_map::HashMap<<S as Iterator>::Item, $T>, ()>
670                where S: Iterator, <S as Iterator>::Item : Hash + Eq
671            {
672                self.do_try_set(s).map_err(|e| {
673                    self.reset_default();
674                    e
675                })
676            }
677
678            fn do_try_set<S>(&mut self, s: S) -> Result<hash_map::HashMap<<S as Iterator>::Item, $T>, ()>
679                where S: Iterator, <S as Iterator>::Item : Hash + Eq
680            {
681                do_try_set!($T, self, s, hash_map::HashMap::new(), hash_map)
682            }
683
684            /// Create a set partition from an iterator of `Ord`-implementing elements.
685            ///
686            /// Returns the set partition and a map from iterator elements to representative values.
687            ///
688            /// Use `from` instead if `Hash` is implemented on the iterator elements.
689            pub fn try_from_ord<S>(s: S) -> Result<($SP, btree_map::BTreeMap<<S as Iterator>::Item, $T>), ()>
690                where S: Iterator, <S as Iterator>::Item : Ord
691            {
692                let mut sp = <$SP>::new();
693                sp.try_set_ord(s).map(|map| (sp, map))
694            }
695
696            fn do_try_set_ord<S>(&mut self, s: S) -> Result<btree_map::BTreeMap<<S as Iterator>::Item, $T>, ()>
697                where S: Iterator, <S as Iterator>::Item : Ord
698            {
699                do_try_set!($T, self, s, btree_map::BTreeMap::new(), btree_map)
700            }
701
702            /// Sets a set partition from an iterator of `Ord`-implementing elements.
703            ///
704            /// Returns a map from iterator elements to representative values.
705            ///
706            /// Use `set` instead if `Hash` is implemented on the iterator elements.
707            pub fn try_set_ord<S>(&mut self, s: S) -> Result<btree_map::BTreeMap<<S as Iterator>::Item, $T>, ()>
708                where S: Iterator, <S as Iterator>::Item : Ord
709            {
710                self.do_try_set_ord(s).map_err(|e| {
711                    self.reset_default();
712                    e
713                })
714            }
715
716            /// Returns the number of non-empty subsets in the set partition.
717            pub fn num_subsets(&self) -> $T {
718                if let Some(al) = self.a.last() {
719                    if *al == self.m {
720                        return al.clone().incremented()
721                    }
722                }
723
724                self.m.clone()
725            }
726
727            /// Returns the subsets data structure, usually representing the subsets if present.
728            pub fn subsets(&self) -> &H {
729                &self.h
730            }
731        }
732
733        $($impl)* $SP
734            $($where)* + PartialOrd<$T> {
735            /// Create a set partition from a canonical representative sequence in an iterator.
736            ///
737            /// Returns Err(()) if the sequence is not a canonical representative sequence.
738            pub fn try_from_repr<I>(iter: I) -> Result<$SP, ()>
739                where I: Iterator<Item = $T>
740            {
741                let mut sp = <$SP>::new();
742                sp.do_try_set_repr(iter).map(|_| sp)
743            }
744
745            /// Checks if a sequence is a canonical representative sequence.
746            pub fn is_repr<I>(iter: I) -> bool
747                where I: Iterator<Item = $T>
748            {
749                let mut m: $T = <$T>::default();
750                let mut n = 0;
751                let max_len = Self::max_len();
752                for ai in iter {
753                    n += 1;
754                    if n > max_len {
755                        return false;
756                    }
757                    if !(ai <= m) {
758                        return false;
759                    }
760                    let ai1 = ai.incremented();
761                    if ai1 > m {
762                        m = ai1;
763                    }
764                }
765                n >= Self::min_len()
766            }
767
768            /// Set the set partition to a canonical representative sequence in an iterator.
769            ///
770            /// Returns Err(()) if the sequence is not a canonical representative sequence,
771            /// and also sets it to the default value
772            pub fn try_set_repr<I>(&mut self, iter: I) -> Result<(), ()>
773                where I: Iterator<Item = $T>
774            {
775                self.do_try_set_repr(iter).map_err(|e| {
776                    self.reset_default();
777                    e
778                })
779            }
780
781            /// Set the set partition to a canonical representative sequence in an iterator.
782            ///
783            /// Returns Err(()) if the sequence is not a canonical representative sequence,
784            /// and also sets it to the default value
785            fn do_try_set_repr<I>(&mut self, mut iter: I) -> Result<(), ()>
786                where I: Iterator<Item = $T>
787            {
788                let mut old_m = <$T>::default();
789                let mut m = <$T>::default().incremented();
790
791                {
792                    let mut i = 0;
793                    #[allow(unused_mut)]
794                    let (mut a, mut b, h) = self.pushers();
795                    {
796                        if let Some(ai) = iter.next() {
797                            if ai != <$T>::default() {
798                                return Err(());
799                            }
800                            h.add(i, &ai);
801                            i += 1;
802                            a.try_push(ai).map_err(|_| ())?;
803                        }
804                    }
805                    for ai in iter {
806                        if old_m == <$T>::default() {
807                            old_m.increment();
808                        }
809                        b.try_push(old_m).map_err(|_| ())?;
810
811                        if !(ai <= m) {
812                            return Err(());
813                        }
814                        h.add(i, &ai);
815                        i += 1;
816                        a.try_push(ai.clone()).map_err(|_| ())?;
817
818                        old_m = m.clone();
819                        let ai1 = ai.incremented();
820                        if ai1 > m {
821                            m = ai1;
822                        }
823                    }
824                    a.done()?;
825                    b.done()?;
826                    h.done(i);
827                    if i != 0 {
828                        h.set_limit(&m);
829                    }
830                }
831                self.m = old_m;
832
833                Ok(())
834            }
835        }
836
837        $($impl)* Incrementable for $SP
838            $($where)* {
839            fn increment(&mut self) {
840                Self::increment(self);
841            }
842        }
843
844        $($impl)* Default for $SP
845            $($where)* {
846            fn default() -> Self {
847                Self::new()
848            }
849        }
850
851        $($impl)* PartialOrd<$SP> for $SP
852            $($where)* + PartialOrd {
853            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
854                self.a.partial_cmp(&other.a)
855            }
856
857            fn lt(&self, other: &Self) -> bool {
858                self.a.lt(&other.a)
859            }
860
861            fn gt(&self, other: &Self) -> bool {
862                self.a.gt(&other.a)
863            }
864
865            fn le(&self, other: &Self) -> bool {
866                self.a.le(&other.a)
867            }
868
869            fn ge(&self, other: &Self) -> bool {
870                self.a.ge(&other.a)
871            }
872        }
873
874        $($impl)* Ord for $SP
875            $($where)* + Ord {
876            fn cmp(&self, other: &Self) -> Ordering {
877                self.a.cmp(&other.a)
878            }
879        }
880
881        $($impl)* PartialEq<$SP> for $SP
882            $($where)* {
883            fn eq(&self, other: &Self) -> bool {
884                self.a.eq(&other.a)
885            }
886
887            fn ne(&self, other: &Self) -> bool {
888                self.a.ne(&other.a)
889            }
890        }
891
892        $($impl)* Eq for $SP
893            $($where)* + Eq {
894        }
895        
896        $($impl)* Hash for $SP
897            $($where)* + Hash {
898            fn hash<HH: Hasher>(&self, state: &mut HH) {
899                self.a.hash(state);
900            }
901        }
902
903        $($impl)* Deref for $SP
904            $($where)* {
905            type Target = [$T];
906
907            fn deref(&self) -> &Self::Target {
908                self.get()
909            }
910        }
911
912        $($impl)* AsRef<[$T]> for $SP
913            $($where)* {
914            fn as_ref(&self) -> &[$T] {
915                self.get()
916            }
917        }
918
919        $($impl)* Borrow<[$T]> for $SP
920            $($where)* {
921            fn borrow(&self) -> &[$T] {
922                self.get()
923            }
924        }
925
926        $($impl)* Index<usize> for $SP
927            $($where)* {
928            type Output = $T;
929
930            fn index(&self, index: usize) -> &$T {
931                &self.get()[index]
932            }
933        }
934
935        $($impl)* Index<ops::Range<usize>> for $SP
936            $($where)* {
937            type Output = [$T];
938
939            fn index(&self, index: ops::Range<usize>) -> &[$T] {
940                Index::index(&**self, index)
941            }
942        }
943
944        $($impl)* Index<ops::RangeTo<usize>> for $SP
945            $($where)* {
946            type Output = [$T];
947
948            fn index(&self, index: ops::RangeTo<usize>) -> &[$T] {
949                Index::index(&**self, index)
950            }
951        }
952
953        $($impl)* Index<ops::RangeFrom<usize>> for $SP
954            $($where)* {
955            type Output = [$T];
956
957            fn index(&self, index: ops::RangeFrom<usize>) -> &[$T] {
958                Index::index(&**self, index)
959            }
960        }
961
962        $($impl)* Index<ops::RangeFull> for $SP
963            $($where)* {
964            type Output = [$T];
965
966            fn index(&self, index: ops::RangeFull) -> &[$T] {
967                Index::index(&**self, index)
968            }
969        }
970
971        $($impl_a)* IntoIterator for &'a $SP
972            $($where)* {
973            type Item = &'a $T;
974            type IntoIter = slice::Iter<'a, $T>;
975
976            fn into_iter(self) -> slice::Iter<'a, $T> {
977                (&self.a).into_iter()
978            }
979        }
980
981        $($impl_a)* IntoIterator for &'a mut $SP
982            $($where)* {
983            type Item = &'a mut $T;
984            type IntoIter = slice::IterMut<'a, $T>;
985
986            fn into_iter(self) -> slice::IterMut<'a, $T> {
987                (&mut self.a).into_iter()
988            }
989        }
990    }
991}
992
993/// Represents a set partition stored in a `Vec`
994///
995/// For small sizes, use `ArrayVecSetPartition` instead.
996///
997/// If the size is constant, use the appropriate `SetPartition#` struct instead for better performance.
998#[derive(Debug, Clone)]
999pub struct VecSetPartition<T = usize, H: Subsets<T> = ()>
1000    where T: Default + Incrementable + PartialEq<T> + Clone
1001{
1002    a: Vec<T>,
1003    b: Vec<T>,
1004    m: T,
1005    h: H
1006}
1007
1008impl<T, H: Subsets<T>> VecSetPartition<T, H>
1009    where T: Default + Incrementable + PartialEq<T> + Clone
1010{
1011    /// Create the trivial set partition of size 0
1012    pub fn new() -> Self {
1013        VecSetPartition {a: Vec::new(), b: Vec::new(), m: T::default(), h: Default::default()}
1014    }
1015
1016    /// Returns the minimum sequence length supported by this type
1017    pub fn min_len() -> usize {0}
1018
1019    /// Returns the maximum sequence length supported by this type
1020    pub fn max_len() -> usize {usize::max_value()}
1021
1022    /// Reset to the trivial set partition of the supported size
1023    pub fn reset_default(&mut self) {
1024        self.a.clear();
1025        self.b.clear();
1026        self.m = T::default();
1027    }
1028
1029    /// Create the trivial set partition of size `n`
1030    pub fn with_size(n: usize) -> Self {
1031        let mut r: Self = VecSetPartition {a: vec![T::default(); n], b: vec![T::default().incremented(); if n > 0 {n - 1} else {0}], m: if n > 1 {T::default().incremented()} else {T::default()}, h: Default::default()};
1032        r.h.reset(n);
1033        r
1034    }
1035
1036    /// Create the trivial set partition of size `n`
1037    pub fn try_with_size(n: usize) -> Result<VecSetPartition<T, H>, ()> {
1038        Ok(Self::with_size(n))
1039    }
1040
1041    /// Reset to the trivial set partition of size `n`
1042    pub fn resize(&mut self, n: usize) {
1043        self.do_reset();
1044        self.a.resize(n, T::default());
1045        self.b.resize(if n > 0 {n - 1} else {0}, T::default().incremented());
1046        self.m = if n > 1 {T::default().incremented()} else {T::default()};
1047        self.h.reset(n);
1048    }
1049
1050    /// Reset to the trivial set partition of size `n`
1051    pub fn try_resize(&mut self, n: usize) -> Result<(), ()> {
1052        self.resize(n);
1053        Ok(())
1054    }
1055
1056    /// Returns the vector storing the representative sequence
1057    pub fn to_vec(self) -> Vec<T> {
1058        self.a
1059    }
1060
1061    fn pushers(&mut self) -> (&mut Vec<T>, &mut Vec<T>, &mut H) {
1062        self.a.clear();
1063        self.b.clear();
1064        self.h.clear();
1065        (&mut self.a, &mut self.b, &mut self.h)
1066    }
1067}
1068
1069impl<T, H: Subsets<T>> IntoIterator for VecSetPartition<T, H>
1070    where T: Default + Incrementable + PartialEq<T> + Clone {
1071    type Item = T;
1072    type IntoIter = std::vec::IntoIter<T>;
1073
1074    fn into_iter(self) -> std::vec::IntoIter<T> {
1075        self.to_vec().into_iter()
1076    }
1077}
1078
1079impl_set_partition!(VecSetPartition<T, H>, T, {impl<T, H: Subsets<T>>}, {impl<'a, T, H: Subsets<T>>}, {where T: Default + Incrementable + PartialEq<T> + Clone});
1080
1081/// Represents a set partition stored in an `ArrayVec`.
1082///
1083/// For big sizes, use `VecSetPartition` instead, which uses a `Vec`.
1084///
1085/// If the size is constant, use the appropriate `SetPartition#` struct instead for better performance.
1086#[derive(Clone)]
1087pub struct ArrayVecSetPartition<T, H: Subsets<T>, const N: usize>
1088    where T: Default + Incrementable + PartialEq<T> + Clone
1089{
1090    a: ArrayVec<T, N>,
1091    b: ArrayVec<T, N>,
1092    m: T,
1093    h: H
1094}
1095
1096// derive doesn't generate the correct where clause
1097impl<T, H: Subsets<T>, const N: usize> Debug for ArrayVecSetPartition<T, H, N>
1098    where H: Debug, T: Default + Incrementable + PartialEq<T> + Clone + Debug
1099{
1100    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1101        f.debug_struct("ArrayVecSetPartition")
1102            .field("a", &self.a)
1103            .field("b", &self.b)
1104            .field("m", &self.m)
1105            .field("h", &self.h)
1106            .finish()
1107    }
1108}
1109
1110impl<T, H: Subsets<T>, const N: usize> ArrayVecSetPartition<T, H, N>
1111    where T: Default + Incrementable + PartialEq<T> + Clone
1112{
1113    /// Create the trivial set partition of size 0
1114    pub fn new() -> Self {
1115        ArrayVecSetPartition {
1116            a: ArrayVec::new(),
1117            b: ArrayVec::new(),
1118            m: T::default(),
1119            h: Default::default()
1120        }
1121    }
1122
1123    /// Returns the minimum sequence length supported by this type
1124    pub fn min_len() -> usize {0}
1125
1126    /// Returns the maximum sequence length supported by this type
1127    pub fn max_len() -> usize {N}
1128
1129    /// Reset to the trivial set partition of the supported size
1130    pub fn reset_default(&mut self) {
1131        self.a.clear();
1132        self.b.clear();
1133        self.m = T::default();
1134    }
1135
1136    /// Create the trivial set partition of size `n`
1137    pub fn try_with_size(n: usize) -> Result<Self, ()> {
1138        let mut r = Self::new();
1139        r.try_resize(n).map(|_| r)
1140    }
1141
1142    /// Reset to the trivial set partition of size `n`
1143    pub fn try_resize(&mut self, n: usize) -> Result<(), ()> {
1144        if n > self.a.capacity() {
1145            return Err(());
1146        }
1147
1148        self.do_reset();
1149        if self.len() == 0 && n != 0 {
1150            self.a.push(T::default());
1151        }
1152        while self.len() > n {
1153            self.a.pop();
1154            self.b.pop();
1155        }
1156        while self.len() < n{
1157            self.a.push(T::default());
1158            self.b.push(T::default().incremented());
1159        }
1160        if n > 1 {
1161            self.m = T::default().incremented();
1162        } else {
1163            self.m = T::default();
1164        }
1165        self.h.reset(self.a.len());
1166        Ok(())
1167    }
1168
1169    /// Returns the vector storing the representative sequence
1170    pub fn to_vec(self) -> ArrayVec<T, N> {
1171        self.a
1172    }
1173
1174    fn pushers(&mut self) -> (&mut ArrayVec<T, N>, &mut ArrayVec<T, N>, &mut H) {
1175        self.a.clear();
1176        self.b.clear();
1177        self.h.clear();
1178        (&mut self.a, &mut self.b, &mut self.h)
1179    }
1180}
1181
1182impl<T, H: Subsets<T>, const N: usize> IntoIterator for ArrayVecSetPartition<T, H, N>
1183    where T: Default + Incrementable + PartialEq<T> + Clone {
1184    type Item = T;
1185    type IntoIter = arrayvec::IntoIter<T, N>;
1186
1187    fn into_iter(self) -> arrayvec::IntoIter<T, N> {
1188        self.to_vec().into_iter()
1189    }
1190}
1191
1192impl_set_partition!(ArrayVecSetPartition<T, H, N>, T, {impl<T, H: Subsets<T>, const N: usize>}, {impl<'a, T, H: Subsets<T>, const N: usize>}, {where T: Default + Incrementable + PartialEq<T> + Clone});
1193
1194/// Represents a set partition stored in a 16-entry `ArrayVec`.
1195///
1196/// For big sizes, use `VecSetPartition` instead, which uses a `Vec`.
1197///
1198/// If the size is constant, use the appropriate `SetPartition#` struct instead for better performance.
1199pub type GenSmallSetPartition<T>
1200    //where T: Default + Incrementable + PartialEq<T> + Clone
1201    = ArrayVecSetPartition<T, (), 16>;
1202
1203/// Represents a set partition stored in a 16-entry `ArrayVec`.
1204///
1205/// For big sizes, use `VecSetPartition` instead, which uses a `Vec`.
1206///
1207/// If the size is constant, use the appropriate `SetPartition#` struct instead for better performance.
1208pub type SmallSetPartition = GenSmallSetPartition<u8>;
1209
1210macro_rules! fixed_set_partition {
1211    ($t:tt, $tu8:tt, $an:expr, $bn:expr, $a:tt, $b:tt, $ac:expr, $bc:expr) => {
1212        /// Represents a fixed size set partition stored in a fixed-size array
1213        #[derive(Debug)]
1214        pub struct $t<T, H: Subsets<T> = ()>
1215            where T: Default + Incrementable + PartialEq<T> + Clone
1216        {
1217            a: [T; $an],
1218            b: [T; $bn],
1219            m: T,
1220            h: H
1221        }
1222
1223        impl<T, H: Subsets<T>> $t<T, H>
1224            where T: Default + Incrementable + PartialEq<T> + Clone
1225        {
1226            /// Create the trivial set partition of the supported size
1227            pub fn new() -> Self {
1228                let mut r = $t {
1229                    a: $a,
1230                    b: $b,
1231                    m: if $an > 1 {T::default().incremented()} else {T::default()},
1232                    h: H::default()
1233                };
1234                r.h.reset($an);
1235                r
1236            }
1237
1238            /// Returns the minimum sequence length supported by this type
1239            pub fn min_len() -> usize {$an}
1240
1241            /// Returns the maximum sequence length supported by this type
1242            pub fn max_len() -> usize {$an}
1243
1244            /// Reset to the trivial set partition of the supported size
1245            pub fn reset_default(&mut self) {
1246                *self = Self::new();
1247            }
1248
1249            /// Returns the array storing the representative sequence
1250            pub fn to_array(self) -> [T; $an] {
1251                self.a
1252            }
1253
1254            fn pushers(&mut self) -> (SlicePusher<T>, SlicePusher<T>, &mut H) {
1255                self.h.clear();
1256                (SlicePusher::new(&mut self.a), SlicePusher::new(&mut self.b), &mut self.h)
1257            }
1258        }
1259
1260        impl<T, H: Subsets<T>> Clone for $t<T, H>
1261            where T: Default + Incrementable + PartialEq<T> + Clone
1262        {
1263            fn clone(&self) -> Self
1264            {
1265                let fa = $ac;
1266                let fb = $bc;
1267                $t {
1268                    a: fa(self),
1269                    b: fb(self),
1270                    m: self.m.clone(),
1271                    h: Default::default()
1272                }
1273            }
1274        }
1275
1276        impl<T, H: Subsets<T>> IntoIterator for $t<T, H>
1277            where T: Default + Incrementable + PartialEq<T> + Clone {
1278            type Item = T;
1279            type IntoIter = arrayvec::IntoIter<T, $an>;
1280
1281            fn into_iter(self) -> arrayvec::IntoIter<T, $an> {
1282                ArrayVec::from(self.to_array()).into_iter()
1283            }
1284        }
1285
1286        impl_set_partition!($t<T, H>, T, {impl<T, H: Subsets<T>>}, {impl<'a, T, H: Subsets<T>>}, {where T: Default + Incrementable + PartialEq<T> + Clone});
1287
1288        /// Represents a fixed size set partition stored in a fixed-size `u8` array
1289        #[derive(Debug, Clone)]
1290        pub struct $tu8<H: Subsets<u8> = ()>
1291        {
1292            a: [u8; $an],
1293            b: [u8; $bn],
1294            m: u8,
1295            h: H
1296        }
1297
1298        impl<H: Subsets<u8>> $tu8<H>
1299        {
1300            /// Create the trivial set partition of the supported size
1301            pub fn new() -> Self {
1302                let mut r = $tu8 {
1303                    a: [0u8; $an],
1304                    b: [1u8; $bn],
1305                    m: if $an > 1 {1u8} else {0u8},
1306                    h: H::default()
1307                };
1308                r.h.reset($an);
1309                r
1310            }
1311
1312            /// Returns the minimum sequence length supported by this type
1313            pub fn min_len() -> usize {$an}
1314
1315            /// Returns the maximum sequence length supported by this type
1316            pub fn max_len() -> usize {$an}
1317
1318            /// Reset to the trivial set partition of the supported size
1319            pub fn reset_default(&mut self) {
1320                *self = Self::new();
1321            }
1322
1323            /// Returns the array storing the representative sequence
1324            pub fn to_array(self) -> [u8; $an] {
1325                self.a
1326            }
1327
1328            fn pushers(&mut self) -> (SlicePusher<u8>, SlicePusher<u8>, &mut H) {
1329                self.h.clear();
1330                (SlicePusher::new(&mut self.a), SlicePusher::new(&mut self.b), &mut self.h)
1331            }
1332        }
1333
1334        impl<H: Subsets<u8>> IntoIterator for $tu8<H>
1335        {
1336            type Item = u8;
1337            type IntoIter = arrayvec::IntoIter<u8, $an>;
1338
1339            fn into_iter(self) -> arrayvec::IntoIter<u8, $an> {
1340                ArrayVec::from(self.to_array()).into_iter()
1341            }
1342        }
1343
1344        impl_set_partition!($tu8<H>, u8, {impl<H: Subsets<u8>>}, {impl<'a, H: Subsets<u8>>}, {where u8: Default + Incrementable + PartialEq<u8> + Clone});
1345    }
1346}
1347
1348// unfortunately we need all this boilerplate to avoid an unnecessary Copy bound on T...
1349fixed_set_partition!(GenSetPartition0, SetPartition0, 0, 0, [], [], |_: &GenSetPartition0<T, H>| [], |_: &GenSetPartition0<T, H>| []);
1350fixed_set_partition!(GenSetPartition1, SetPartition1, 1, 0, [T::default()], [], |s: &GenSetPartition1<T, H>| [s.a[0].clone()], |_: &GenSetPartition1<T, H>| []);
1351// generated with for i in `seq 2 32`; do echo "fixed_set_partition!(SetPartition$i, $i, $(($i - 1)), [$(for j in `seq 2 $i`; do echo -n "T::default(), "; done)T::default()], [$(for j in `seq 3 $i`; do echo -n "T::default().incremented(), "; done)T::default().incremented()], |s: &GenSetPartition$i<T, H>| [s.a[0].clone()$(for j in `seq 1 $(($i-1))`; do echo -n ", s.a[$j].clone()"; done)], |s: &GenSetPartition$i<T, H>| [s.b[0].clone()$(for j in `seq 1 $(($i-2))`; do echo -n ", s.b[$j].clone()"; done)]);"; done
1352fixed_set_partition!(GenSetPartition2, SetPartition2, 2, 1, [T::default(), T::default()], [T::default().incremented()], |s: &GenSetPartition2<T, H>| [s.a[0].clone(), s.a[1].clone()], |s: &GenSetPartition2<T, H>| [s.b[0].clone()]);
1353fixed_set_partition!(GenSetPartition3, SetPartition3, 3, 2, [T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented()], |s: &GenSetPartition3<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone()], |s: &GenSetPartition3<T, H>| [s.b[0].clone(), s.b[1].clone()]);
1354fixed_set_partition!(GenSetPartition4, SetPartition4, 4, 3, [T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition4<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone()], |s: &GenSetPartition4<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone()]);
1355fixed_set_partition!(GenSetPartition5, SetPartition5, 5, 4, [T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition5<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone()], |s: &GenSetPartition5<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone()]);
1356fixed_set_partition!(GenSetPartition6, SetPartition6, 6, 5, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition6<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone()], |s: &GenSetPartition6<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone()]);
1357fixed_set_partition!(GenSetPartition7, SetPartition7, 7, 6, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition7<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone()], |s: &GenSetPartition7<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone()]);
1358fixed_set_partition!(GenSetPartition8, SetPartition8, 8, 7, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition8<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone()], |s: &GenSetPartition8<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone()]);
1359fixed_set_partition!(GenSetPartition9, SetPartition9, 9, 8, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition9<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone()], |s: &GenSetPartition9<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone()]);
1360fixed_set_partition!(GenSetPartition10, SetPartition10, 10, 9, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition10<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone()], |s: &GenSetPartition10<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone()]);
1361fixed_set_partition!(GenSetPartition11, SetPartition11, 11, 10, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition11<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone()], |s: &GenSetPartition11<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone()]);
1362fixed_set_partition!(GenSetPartition12, SetPartition12, 12, 11, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition12<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone()], |s: &GenSetPartition12<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone()]);
1363fixed_set_partition!(GenSetPartition13, SetPartition13, 13, 12, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition13<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone()], |s: &GenSetPartition13<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone()]);
1364fixed_set_partition!(GenSetPartition14, SetPartition14, 14, 13, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition14<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone()], |s: &GenSetPartition14<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone()]);
1365fixed_set_partition!(GenSetPartition15, SetPartition15, 15, 14, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition15<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone()], |s: &GenSetPartition15<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone()]);
1366fixed_set_partition!(GenSetPartition16, SetPartition16, 16, 15, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition16<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone()], |s: &GenSetPartition16<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone()]);
1367fixed_set_partition!(GenSetPartition17, SetPartition17, 17, 16, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition17<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone()], |s: &GenSetPartition17<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone()]);
1368fixed_set_partition!(GenSetPartition18, SetPartition18, 18, 17, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition18<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone()], |s: &GenSetPartition18<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone()]);
1369fixed_set_partition!(GenSetPartition19, SetPartition19, 19, 18, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition19<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone()], |s: &GenSetPartition19<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone()]);
1370fixed_set_partition!(GenSetPartition20, SetPartition20, 20, 19, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition20<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone()], |s: &GenSetPartition20<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone()]);
1371fixed_set_partition!(GenSetPartition21, SetPartition21, 21, 20, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition21<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone()], |s: &GenSetPartition21<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone()]);
1372fixed_set_partition!(GenSetPartition22, SetPartition22, 22, 21, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition22<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone()], |s: &GenSetPartition22<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone()]);
1373fixed_set_partition!(GenSetPartition23, SetPartition23, 23, 22, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition23<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone()], |s: &GenSetPartition23<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone()]);
1374fixed_set_partition!(GenSetPartition24, SetPartition24, 24, 23, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition24<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone()], |s: &GenSetPartition24<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone()]);
1375fixed_set_partition!(GenSetPartition25, SetPartition25, 25, 24, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition25<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone()], |s: &GenSetPartition25<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone()]);
1376fixed_set_partition!(GenSetPartition26, SetPartition26, 26, 25, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition26<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone()], |s: &GenSetPartition26<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone()]);
1377fixed_set_partition!(GenSetPartition27, SetPartition27, 27, 26, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition27<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone()], |s: &GenSetPartition27<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone()]);
1378fixed_set_partition!(GenSetPartition28, SetPartition28, 28, 27, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition28<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone(), s.a[27].clone()], |s: &GenSetPartition28<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone(), s.b[26].clone()]);
1379fixed_set_partition!(GenSetPartition29, SetPartition29, 29, 28, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition29<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone(), s.a[27].clone(), s.a[28].clone()], |s: &GenSetPartition29<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone(), s.b[26].clone(), s.b[27].clone()]);
1380fixed_set_partition!(GenSetPartition30, SetPartition30, 30, 29, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition30<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone(), s.a[27].clone(), s.a[28].clone(), s.a[29].clone()], |s: &GenSetPartition30<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone(), s.b[26].clone(), s.b[27].clone(), s.b[28].clone()]);
1381fixed_set_partition!(GenSetPartition31, SetPartition31, 31, 30, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition31<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone(), s.a[27].clone(), s.a[28].clone(), s.a[29].clone(), s.a[30].clone()], |s: &GenSetPartition31<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone(), s.b[26].clone(), s.b[27].clone(), s.b[28].clone(), s.b[29].clone()]);
1382fixed_set_partition!(GenSetPartition32, SetPartition32, 32, 31, [T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default(), T::default()], [T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented(), T::default().incremented()], |s: &GenSetPartition32<T, H>| [s.a[0].clone(), s.a[1].clone(), s.a[2].clone(), s.a[3].clone(), s.a[4].clone(), s.a[5].clone(), s.a[6].clone(), s.a[7].clone(), s.a[8].clone(), s.a[9].clone(), s.a[10].clone(), s.a[11].clone(), s.a[12].clone(), s.a[13].clone(), s.a[14].clone(), s.a[15].clone(), s.a[16].clone(), s.a[17].clone(), s.a[18].clone(), s.a[19].clone(), s.a[20].clone(), s.a[21].clone(), s.a[22].clone(), s.a[23].clone(), s.a[24].clone(), s.a[25].clone(), s.a[26].clone(), s.a[27].clone(), s.a[28].clone(), s.a[29].clone(), s.a[30].clone(), s.a[31].clone()], |s: &GenSetPartition32<T, H>| [s.b[0].clone(), s.b[1].clone(), s.b[2].clone(), s.b[3].clone(), s.b[4].clone(), s.b[5].clone(), s.b[6].clone(), s.b[7].clone(), s.b[8].clone(), s.b[9].clone(), s.b[10].clone(), s.b[11].clone(), s.b[12].clone(), s.b[13].clone(), s.b[14].clone(), s.b[15].clone(), s.b[16].clone(), s.b[17].clone(), s.b[18].clone(), s.b[19].clone(), s.b[20].clone(), s.b[21].clone(), s.b[22].clone(), s.b[23].clone(), s.b[24].clone(), s.b[25].clone(), s.b[26].clone(), s.b[27].clone(), s.b[28].clone(), s.b[29].clone(), s.b[30].clone()]);
1383
1384// bigger ones don't fit into u64
1385static BELL_NUMBERS: [u64; 26] = [
1386    1,
1387    1,
1388    2,
1389    5,
1390    15,
1391    52,
1392    203,
1393    877,
1394    4140,
1395    21147,
1396    115975,
1397    678570,
1398    4213597,
1399    27644437,
1400    190899322,
1401    1382958545,
1402    10480142147,
1403    82864869804,
1404    682076806159,
1405    5832742205057,
1406    51724158235372,
1407    474869816156751,
1408    4506715738447323,
1409    44152005855084346,
1410    445958869294805289,
1411    4638590332229999353
1412];
1413
1414/// Number of partitions of a set of `n` elements.
1415///
1416/// Simply returns the `n`-th Bell number, or `None`. if it's too large to fit into `u64`.
1417pub fn set_partitions(n: usize) -> Option<u64>
1418{
1419    BELL_NUMBERS.get(n).map(|x| *x)
1420}
1421
1422// for enumeration it's required and sufficient to test that we are enumerating all restricted growth sequences of length n in lexicographic order
1423// the number of test iterations varies due to the varying execution speeds of the test subsets loops
1424#[cfg(test)]
1425mod tests {
1426    macro_rules! test {
1427        ($T:ty, $new:expr) => {
1428            fn check_subsets(s: &$T) {
1429                super::check_subsets(s.get(), s.subsets());
1430            }
1431
1432            fn range(n: usize) -> ::std::ops::Range<usize> {
1433                let a = <$T>::min_len();
1434                let mut b = <$T>::max_len();
1435                if n <= b {
1436                    b = n - 1;
1437                }
1438                a..(b+1)
1439            }
1440
1441            #[test]
1442            fn subsets() {
1443                for n in range(9) {
1444                    let mut s = $new(n);
1445
1446                    loop {
1447                        check_subsets(&s);
1448                        if !s.increment() {break;}
1449                    }
1450                    check_subsets(&s);
1451                }
1452            }
1453
1454            #[test]
1455            fn zeroes() {
1456                for n in range(12) {
1457                    let mut s = $new(n);
1458
1459                    assert_eq!(s.get().len(), n);
1460                    assert!(s.get().iter().all(|x| *x == Default::default()));
1461
1462                    loop {
1463                        if !s.increment() {break;}
1464                    }
1465
1466                    assert_eq!(s.get().len(), n);
1467                    assert!(s.get().iter().all(|x| *x == Default::default()));
1468                }
1469            }
1470
1471            #[test]
1472            fn lexicographic() {
1473                for n in range(10) {
1474                    let mut s = $new(n);
1475                    let mut last = Vec::new();
1476                    loop {
1477                        if s.len() > 0 {
1478                            assert!(&*last < s.get());
1479                        }
1480                        last.clear();
1481                        last.extend_from_slice(s.get());
1482
1483                        if !s.increment() {break;}
1484                    }
1485                }
1486            }
1487
1488            #[test]
1489            fn restricted_growth_of_len_n() {
1490                use std::cmp::max;
1491                for n in range(11) {
1492                    let mut s = $new(n);
1493
1494                    loop {
1495                        let mut m = 0;
1496                        assert_eq!(s.get().len(), n);
1497
1498                        for ai in s.get() {
1499                            assert!(*ai <= m);
1500                            m = max(m, (*ai).clone() + 1);
1501                        }
1502
1503                        if !s.increment() {break;}
1504                    }
1505                }
1506            }
1507
1508            #[test]
1509            fn all() {
1510                for n in range(12) {
1511                    let mut s = $new(n);
1512                    let mut i = 0;
1513                    loop {
1514                        i += 1;
1515                        if !s.increment() {break;}
1516                    }
1517
1518                    assert_eq!(Some(i), crate::set_partitions(s.len()));
1519                }
1520            }
1521
1522            #[test]
1523            fn try_set_repr() {
1524                for n in range(9) {
1525                    let mut s = $new(n);
1526                    let mut sets = $new(n);
1527                    loop {
1528                        let seq = s.get().iter().map(|x| *x).collect::<Vec<_>>();
1529                        assert!(sets.try_set_repr(seq.into_iter()).is_ok());
1530                        assert_eq!((&s.a, &s.b, &s.m), (&sets.a, &sets.b, &sets.m));
1531                        check_subsets(&sets);
1532                        if !s.increment() {break;}
1533                    }
1534                }
1535            }
1536
1537            #[test]
1538            fn try_set() {
1539                for n in range(9) {
1540                    let mut s = $new(n);
1541                    let mut sets = $new(n);
1542                    loop {
1543                        assert!(sets.try_set(s.get().iter()).is_ok());
1544                        assert_eq!((&s.a, &s.b, &s.m), (&sets.a, &sets.b, &sets.m));
1545                        println!("{} {:?}", n, &sets);
1546                        check_subsets(&sets);
1547                        if !s.increment() {break;}
1548                    }
1549                }
1550            }
1551
1552            #[test]
1553            fn try_set_ord() {
1554                for n in range(9) {
1555                    let mut s = $new(n);
1556                    let mut sets = $new(n);
1557                    loop {
1558                        assert!(sets.try_set_ord(s.get().iter()).is_ok());
1559                        assert_eq!((&s.a, &s.b, &s.m), (&sets.a, &sets.b, &sets.m));
1560                        check_subsets(&sets);
1561                        if !s.increment() {break;}
1562                    }
1563                }
1564            }
1565
1566            #[test]
1567            fn reset() {
1568                for n in range(9) {
1569                    let mut s = $new(n);
1570                    let new = $new(n);
1571                    loop {
1572                        let mut r = s.clone();
1573                        r.reset();
1574                        assert_eq!((&new.a, &new.b, &new.m), (&r.a, &r.b, &r.m));
1575                        check_subsets(&r);
1576                        if !s.increment() {break;}
1577                    }
1578                }
1579            }
1580        }
1581    }
1582
1583    macro_rules! test_var_size {
1584        ($T:ty, $new:expr) => {
1585            test!($T, $new);
1586
1587            #[test]
1588            fn len() {
1589                for n in range(12) {
1590                    let s = $new(n);
1591                    assert_eq!(s.len(), n);
1592                }
1593            }
1594
1595            #[test]
1596            fn resize() {
1597                for n in range(8) {
1598                    let mut s = $new(n);
1599                    loop {
1600                        for m in 0..16 {
1601                            let mut r = s.clone();
1602                            assert!(r.try_resize(m).is_ok());
1603                            check_subsets(&r);
1604                            let sm = $new(m);
1605                            assert_eq!((&sm.a, &sm.b, &sm.m), (&r.a, &r.b, &r.m));
1606                        }
1607                        if !s.increment() {break;}
1608                    }
1609                }
1610            }
1611        }
1612    }
1613
1614    macro_rules! test_subsets {
1615        ($S:ty, $E:ty) => {
1616            fn new_small(n: usize) -> crate::ArrayVecSetPartition<[$E; 16], $S> {
1617                crate::ArrayVecSetPartition::try_with_size(n).unwrap()
1618            }
1619
1620            fn new<T: Default>(_: usize) -> T {
1621                T::default()
1622            }
1623
1624            mod avecsp {test_var_size!(crate::ArrayVecSetPartition<[$E; 16], $S>, super::new_small);}
1625            mod vecsp {test_var_size!(crate::VecSetPartition<$E, $S>, crate::VecSetPartition::<$E, $S>::with_size);}
1626
1627            // generated with for i in `seq 0 9`; do echo "mod sp$i {test!(::SetPartition$i<\$S>, super::new::<::SetPartition$i<\$S>>);} mod gsp$i {test!(::GenSetPartition$i<\$E, \$S>, super::new::<::GenSetPartition$i<\$E, \$S>>);}"; done
1628            mod sp0 {test!(crate::SetPartition0<$S>, super::new::<crate::SetPartition0<$S>>);} mod gsp0 {test!(crate::GenSetPartition0<$E, $S>, super::new::<crate::GenSetPartition0<$E, $S>>);}
1629            mod sp1 {test!(crate::SetPartition1<$S>, super::new::<crate::SetPartition1<$S>>);} mod gsp1 {test!(crate::GenSetPartition1<$E, $S>, super::new::<crate::GenSetPartition1<$E, $S>>);}
1630            mod sp2 {test!(crate::SetPartition2<$S>, super::new::<crate::SetPartition2<$S>>);} mod gsp2 {test!(crate::GenSetPartition2<$E, $S>, super::new::<crate::GenSetPartition2<$E, $S>>);}
1631            mod sp3 {test!(crate::SetPartition3<$S>, super::new::<crate::SetPartition3<$S>>);} mod gsp3 {test!(crate::GenSetPartition3<$E, $S>, super::new::<crate::GenSetPartition3<$E, $S>>);}
1632            mod sp4 {test!(crate::SetPartition4<$S>, super::new::<crate::SetPartition4<$S>>);} mod gsp4 {test!(crate::GenSetPartition4<$E, $S>, super::new::<crate::GenSetPartition4<$E, $S>>);}
1633            mod sp5 {test!(crate::SetPartition5<$S>, super::new::<crate::SetPartition5<$S>>);} mod gsp5 {test!(crate::GenSetPartition5<$E, $S>, super::new::<crate::GenSetPartition5<$E, $S>>);}
1634            mod sp6 {test!(crate::SetPartition6<$S>, super::new::<crate::SetPartition6<$S>>);} mod gsp6 {test!(crate::GenSetPartition6<$E, $S>, super::new::<crate::GenSetPartition6<$E, $S>>);}
1635            mod sp7 {test!(crate::SetPartition7<$S>, super::new::<crate::SetPartition7<$S>>);} mod gsp7 {test!(crate::GenSetPartition7<$E, $S>, super::new::<crate::GenSetPartition7<$E, $S>>);}
1636            mod sp8 {test!(crate::SetPartition8<$S>, super::new::<crate::SetPartition8<$S>>);} mod gsp8 {test!(crate::GenSetPartition8<$E, $S>, super::new::<crate::GenSetPartition8<$E, $S>>);}
1637            mod sp9 {test!(crate::SetPartition9<$S>, super::new::<crate::SetPartition9<$S>>);} mod gsp9 {test!(crate::GenSetPartition9<$E, $S>, super::new::<crate::GenSetPartition9<$E, $S>>);}
1638        }
1639    }
1640
1641    mod noss {
1642        fn check_subsets<T>(_: &[T], _: &()) {}
1643
1644        test_subsets!((), u16);
1645    }
1646
1647    fn compute_subsets(s: &[u8]) -> Vec<Vec<u8>> {
1648        let mut r = Vec::new();
1649        r.resize(s.len(), Vec::new());
1650        let mut idx = 0;
1651        for i in s {
1652            r[*i as usize].push(idx);
1653            idx += 1;
1654        }
1655
1656        loop {
1657            if let Some(last) = r.last_mut() {
1658                if !last.is_empty() {break;}
1659            } else {
1660                break;
1661            }
1662            r.pop();
1663        }
1664        r
1665    }
1666
1667    mod vecss {
1668        fn check_subsets(s: &[u8], ss: &crate::VecSubsets<u8>) {
1669            let r = super::compute_subsets(s);
1670
1671            assert_eq!(ss.subsets(), &*r);
1672        }
1673
1674        test_subsets!(crate::VecSubsets<u8>, u8);
1675    }
1676
1677    mod avecss {
1678        use ::arrayvec::ArrayVec;
1679        fn check_subsets(s: &[u8], ss: &crate::ArrayVecSubsets<[ArrayVec<[u8; 16]>; 16], [u8; 16]>) {
1680            let r: ArrayVec<[ArrayVec<[u8; 16]>; 16]> = super::compute_subsets(s).into_iter().map(|ss| ss.into_iter().collect()).collect();
1681
1682            assert_eq!(ss.subsets(), &*r);
1683        }
1684
1685        test_subsets!(crate::ArrayVecSubsets<[::arrayvec::ArrayVec<[u8; 16]>; 16], [u8; 16]>, u8);
1686    }
1687
1688    mod hashss {
1689        use ::std::collections::HashSet;
1690        fn check_subsets(s: &[u8], ss: &crate::HashSubsets<u8>) {
1691            let r: Vec<HashSet<u8>> = super::compute_subsets(s).into_iter().map(|ss| ss.into_iter().collect()).collect();
1692
1693            assert_eq!(ss.subsets(), &*r);
1694        }
1695
1696        test_subsets!(crate::HashSubsets<u8>, u8);
1697    }
1698
1699    mod btreess {
1700        use ::std::collections::BTreeSet;
1701        fn check_subsets(s: &[u8], ss: &crate::BTreeSubsets<u8>) {
1702            let r: Vec<BTreeSet<u8>> = super::compute_subsets(s).into_iter().map(|ss| ss.into_iter().collect()).collect();
1703
1704            assert_eq!(ss.subsets(), &*r);
1705        }
1706
1707        test_subsets!(crate::BTreeSubsets<u8>, u8);
1708    }
1709
1710    #[test]
1711    fn set_partitions()
1712    {
1713        let mut bell_numbers = vec![1u64];
1714        let mut n = 0;
1715
1716        assert_eq!(crate::set_partitions(0), Some(1));
1717        loop {
1718            if let Some(sp) = crate::set_partitions(n + 1) {
1719                let mut b = 0u64;
1720                for k in 0..(n+1) {
1721                    let mut c = 1u64;
1722                    for i in 1..k+1 {
1723                        c *= (n - k + i) as u64;
1724                        c /= i as u64;
1725                    }
1726                    b += bell_numbers[k] * c;
1727                }
1728                assert_eq!(b, sp);
1729                bell_numbers.push(b);
1730            } else {
1731                break;
1732            }      
1733            n += 1;
1734        }
1735    }
1736}
set_partitions/lib.rs

set_partitions/
lib.rs
