A primitive integer bitset for high-performance combinatorics
The pibs Rust crate offers a generic BitSet<W> wrapper struct around a
primitive integer type W for representing a set of small numbers. It also
provides the default types Set (W = usize) and Set128 (W = u128) and
associated creation macros bitset!, set!, and set128!. The crate's
main features are
- zero-cost abstraction over bitwise operations without allocation or block management and
- a rich interface for mathematics/combinatorics involving integer sets.
The crate is best suited when the bitset should abstract a mathematical set, the
performance of set operations is your primary concern, and the elements
naturally lie in the representable range (0..128 for Set128).
Example
The following computes by brute force a minimum-cardinality set of positive
integers that generate (by taking any subset of the numbers and summing them)
all elements of a target set. This is done using the iter_combinations(n, k)
generator, which yields all subsets of 0..n (here shifted to 1..=n) of size
k, and the truncating_subset_sums operator, which produces all subset sums
that can be represented by the bitset.
use *;
// To generate {0, ..., 9}, we need a generating set of size four.
assert_eq!;
// But if we don't need to generate 2 and 7, three numbers suffice.
assert_eq!;
See the full documentation for more examples.
Installation
Via one of the following cargo commands:
Or by adding one of the following lines to Cargo.toml (replace 0.1 with the
latest version):
[]
= "0.1" # with default features
= { = "0.1", = false } # without default features
= { = "0.1", = ["serde"] } # with 'serde' feature
Features and dependencies
| feature | default | implements |
|---|---|---|
alloc |
yes | conversion to and from Vec |
serde |
no | (de)serialization via serde |
The crate is no_std-compatible and its only non-optional dependency is
num_traits.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.