Function malachite_base::sets::exhaustive::lex_hash_sets_length_range

source · [−]

pub fn lex_hash_sets_length_range<I: Clone + Iterator>(
    a: u64, 
    b: u64, 
    xs: I
) -> LexOrderedUniqueCollections<I, HashSet<I::Item>>ⓘNotable traits for LexOrderedUniqueCollections<I, C>impl<I: Iterator, C: FromIterator<I::Item>> Iterator for LexOrderedUniqueCollections<I, C> where
    I::Item: Clone,     type Item = C; where
    I::Item: Clone + Eq + Hash,

Expand description

Generates HashSets, with lengths in a range $[a, b)$, with elements from a single iterator.

The HashSets are ordered lexicographically with respect to the order of the element iterator.

The source iterator should not repeat any elements, but this is not enforced.

The iterator should be finite; if it is infinite, only prefixes of the iterator will be generated.

If $a \leq b$, the output is empty.

If $a = 0$ and $b = 1$, the output consists of a single empty HashSet.

If the input iterator is infinite and $0 < a < b$, the output length is also infinite.

If the input iterator length is $n$, the output length is $$ \sum_{i=a}^b - 1 \binom{n}{i}. $$

Examples

extern crate itertools;
#[macro_use]
extern crate maplit;

use itertools::Itertools;
use malachite_base::sets::exhaustive::lex_hash_sets_length_range;

fn main() {
    let xss = lex_hash_sets_length_range(2, 4, 1..=4).collect_vec();
    assert_eq!(
        xss,
        &[
            hashset!{1, 2},
            hashset!{1, 2, 3},
            hashset!{1, 2, 4},
            hashset!{1, 3},
            hashset!{1, 3, 4},
            hashset!{1, 4},
            hashset!{2, 3},
            hashset!{2, 3, 4},
            hashset!{2, 4},
            hashset!{3, 4},
        ]
    );
}