combinadics/
lib.rs

1//! This crate provides methods to de- and encode numbers in the [combinatorial
2//! number system](https://en.wikipedia.org/wiki/Combinatorial_number_system),
3//! sometime referred to as "combinadics".
4
5#![cfg_attr(feature = "nightly", feature(test))]
6#[cfg(feature = "nightly")] extern crate test as rust_test;
7
8extern crate binomial_iter;
9
10use binomial_iter::{BinomialIter, DecNIter};
11
12/// Iterates through all choices decoded from the given `N` and `k` in
13/// descending order.
14#[allow(non_snake_case)]
15pub struct DecodeIter {
16    N: u32,
17    // The `n` holds the state for the 'remaining' iteration, see `next`.
18    n: u32,
19    bin: DecNIter,
20}
21
22/// Returns an iterator over the choices decoded from the given `N` and `k`.
23/// The choices will be returned by the iterator in descending order.
24///
25/// # Panics
26/// If `k == 0`
27#[allow(non_snake_case)]
28pub fn decode(N: u32, k: u32) -> DecodeIter {
29    assert!(k > 0, "invalid argument: `k == 0`");
30
31    let mut bin = BinomialIter::new(k, k);
32
33    // find the largest possible n
34    while bin.binom() < N {
35        bin.inc_n().expect("N too large to decode");
36    }
37
38    DecodeIter {
39        N: N,
40        n: bin.n(), // Initialize n to it's largest possible bin.n
41        bin: bin.iter_dec_n(),
42    }
43}
44
45impl Iterator for DecodeIter {
46    type Item = u32;
47
48    #[inline]
49    fn next(&mut self) -> Option<u32> {
50        // find the next choice
51        while let Some((n, binom)) = self.bin.next() {
52            if binom <= self.N {
53                self.bin.dec_k();
54                self.N -= binom;
55                return Some(n);
56            }
57        }
58
59        // `BinomialIter` does not support `n < k` so there may still be some
60        // choices left, to be precise, all `x < bin.n` still need to be printed.
61        // The first time this path is reached, initialize `self.n`.
62        if self.n > self.bin.n() {
63            self.n = self.bin.n();
64        }
65
66        if self.n > 0 {
67            self.n -= 1;
68            Some(self.n)
69        } else {
70            None
71        }
72    }
73}
74
75#[cfg(all(test, feature = "nightly"))]
76mod bench;
77
78#[cfg(test)]
79mod test;
combinadics/lib.rs

combinadics/
lib.rs
