Crate set_partitions
source · [−]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
Module for the Incrementable trait
Structs
Represents a set partition stored in an ArrayVec.
Maintains subsets of a set partition using ArrayVecs
Maintains subsets of a set partition using BTreeSets
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Represents a fixed size set partition stored in a fixed-size array
Maintains subsets of a set partition using HashSets
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a fixed size set partition stored in a fixed-size u8 array
Represents a set partition stored in a Vec
Maintains subsets of a set partition using Vecs
Traits
Trait used by SetPartition structs to notify the subsets structure of changes.
Functions
Number of partitions of a set of n elements.
Type Definitions
Represents a set partition stored in a 16-entry ArrayVec.
Maintains subsets of a set partition using 16-entry ArrayVecs
Represents a set partition stored in a 16-entry ArrayVec.
Maintains subsets of a set partition using 16-entry ArrayVecs