Expand description
The set-partition crate provides ways to represent, enumerate and count all the possible partitions of a set of a given finite size into subsets.
You can use the set_partitions function to get the number of partitions of a set
with n elements, and you can use the SetPartition struct and its increment()
function to enumerate them (as well as its more generic variants).
Set partitions are represented as sequences of values, with one value for each element of the partitioned set, such that if two elements are in the same subset, the sequence will have the same values at the corresponding indices.
Among all the possible sequences, the one which is lexicographically minimal, and uses values starting from Default::default() and incrementing with increment(), is chosen as the representative.
See http://www-cs-faculty.stanford.edu/~uno/fasc3b.ps.gz page 27 for more information and a description of the algorithm used here.
§How to use
For fixed size set partitions, use SetPartition#; use GenSetPartition# if you want to use something other than u8 as the data type.
For variable size set partitions up to 16 elements (more than 16 result in more than 2^32 partitions), use SmallSetPartition or GenSetPartition,
For medium sized variable size set partitions, use ArrayVecSetPartition.
For arbitrary sized set partitions, use VecSetPartition.
If you don’t care about getting the subset contents, pass () or omit the type parameter.
Otherwise, use SmallSubsets or GenSmallSubsets to represent subsets using ArrayVecs without memory allocation, for set partitions of size 16 or less.
For subsets in other data structures, you can use ArrayVecSubsets, VecSubsets,HashSubsets or BTreeSubsets.
To enumerate set partitions, call increment() until it returns false, and use get(), num_subsets() or subsets().subsets() to examine the set partition.
Modules§
- traits
- Module for the Incrementable trait
Structs§
- Array
VecSet Partition - Represents a set partition stored in an
ArrayVec. - Array
VecSubsets - Maintains subsets of a set partition using
ArrayVecs - BTree
Subsets - Maintains subsets of a set partition using
BTreeSets - GenSet
Partition0 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition1 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition2 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition3 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition4 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition5 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition6 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition7 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition8 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition9 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition10 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition11 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition12 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition13 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition14 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition15 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition16 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition17 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition18 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition19 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition20 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition21 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition22 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition23 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition24 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition25 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition26 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition27 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition28 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition29 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition30 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition31 - Represents a fixed size set partition stored in a fixed-size array
- GenSet
Partition32 - Represents a fixed size set partition stored in a fixed-size array
- Hash
Subsets - Maintains subsets of a set partition using
HashSets - SetPartition0
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition1
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition2
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition3
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition4
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition5
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition6
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition7
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition8
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition9
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition10
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition11
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition12
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition13
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition14
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition15
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition16
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition17
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition18
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition19
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition20
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition21
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition22
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition23
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition24
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition25
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition26
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition27
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition28
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition29
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition30
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition31
- Represents a fixed size set partition stored in a fixed-size
u8array - SetPartition32
- Represents a fixed size set partition stored in a fixed-size
u8array - VecSet
Partition - Represents a set partition stored in a
Vec - VecSubsets
- Maintains subsets of a set partition using
Vecs
Traits§
- Subsets
- Trait used by
SetPartitionstructs to notify the subsets structure of changes.
Functions§
- set_
partitions - Number of partitions of a set of
nelements.
Type Aliases§
- GenSmall
SetPartition - Represents a set partition stored in a 16-entry
ArrayVec. - GenSmall
Subsets - Maintains subsets of a set partition using 16-entry
ArrayVecs - Small
SetPartition - Represents a set partition stored in a 16-entry
ArrayVec. - Small
Subsets - Maintains subsets of a set partition using 16-entry
ArrayVecs