Function malachite_base::vecs::exhaustive::lex_unique_vecs

pub fn lex_unique_vecs<I: Clone + Iterator>(xs: I) -> LexUniqueVecs<I> 
where
    I::Item: Clone,

Generates Vecs with elements from a single iterator, such that each Vec has no repeated elements.

The Vecs 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 the input iterator is infinite, the output length is also infinite.

If the input iterator length is $n$, the output length is $$ \sum_ {k=0}^n \frac{n!}{k!} $$ $$ = \begin{cases} 1 & \text{if} \quad n = 0, \\ 2 & \text{if} \quad n = 1, \\ \operatorname{round}(en!) & \text{otherwise}. \end{cases} $$

See https://oeis.org/A000522.

If xs is empty, the output consists of a single empty Vec.

Examples

use itertools::Itertools;
use malachite_base::vecs::exhaustive::lex_unique_vecs;

let xss = lex_unique_vecs(1..=4).take(20).collect_vec();
assert_eq!(
    xss.iter().map(Vec::as_slice).collect_vec().as_slice(),
    &[
        &[][..],
        &[1],
        &[1, 2],
        &[1, 2, 3],
        &[1, 2, 3, 4],
        &[1, 2, 4],
        &[1, 2, 4, 3],
        &[1, 3],
        &[1, 3, 2],
        &[1, 3, 2, 4],
        &[1, 3, 4],
        &[1, 3, 4, 2],
        &[1, 4],
        &[1, 4, 2],
        &[1, 4, 2, 3],
        &[1, 4, 3],
        &[1, 4, 3, 2],
        &[2],
        &[2, 1],
        &[2, 1, 3]
    ]
);