set-partitions

set-partitions is crate that allows to represent and enumerate partitions of a set

Partitions are represented as slices containing restricted growth sequences, enumerated in lexicographic order, using the algorithm from The Art of Computer Programming Fascicle 3b, page 27, by Donald Knuth.

lib.rs:

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.