Function malachite_base::strings::exhaustive::shortlex_strings

source · [−]

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

Expand description

Generates Strings 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 order of exhaustive_chars, which is not the default lexicographic order for chars. (For example, the first characters are not control characters, but lowercase Latin letters.) If you want the default char order, use shortlex_strings_using_chars(chars_increasing()).

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;

let ss = shortlex_strings().take(20).collect_vec();
assert_eq!(
    ss.iter().map(String::as_str).collect_vec().as_slice(),
    &[
        "", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p",
        "q", "r", "s"
    ]
);