Function malachite_base::strings::exhaustive::shortlex_strings_using_chars

source · [−]

pub fn shortlex_strings_using_chars<I: Clone + Iterator<Item = char>>(
    cs: I
) -> StringsFromCharVecs<ShortlexVecs<char, PrimitiveIntIncreasingRange<u64>, I>>ⓘNotable traits for StringsFromCharVecs<I>impl<I: Iterator<Item = Vec<char>>> Iterator for StringsFromCharVecs<I>    type Item = String;

Expand description

Generates Strings with chars from a specified iterator, in shortlex order.

Shortlex order means that the Strings are output from shortest to longest, and Strings of the same length are output in lexicographic order with respect to the ordering of the chars specified by the input iterator.

cs must be finite; if it’s infinite, only Strings of length 0 and 1 are ever produced.

If cs is empty, the output length is 1; otherwise, the output is infinite.

The lengths of the output Strings grow logarithmically.

Complexity per iteration

$T(i) = O(\log i)$

$M(i) = O(\log i)$

where $T$ is time and $M$ is additional memory.

Examples

extern crate itertools;

use itertools::Itertools;
use malachite_base::strings::exhaustive::shortlex_strings_using_chars;

let ss = shortlex_strings_using_chars('x'..='z')
    .take(20)
    .collect_vec();
assert_eq!(
    ss.iter().map(String::as_str).collect_vec().as_slice(),
    &[
        "", "x", "y", "z", "xx", "xy", "xz", "yx", "yy", "yz", "zx", "zy", "zz", "xxx", "xxy",
        "xxz", "xyx", "xyy", "xyz", "xzx"
    ]
);