Module malachite_base::tuples::exhaustive

source ·
Expand description

Iterators that generate tuples without repetition.

To reduce binary size and lower compilation time, many of the functions described here are not actually defined in Malachite, but may be created in your program using macros exported from Malachite. To do this, see the documentation for lex_tuples and lex_custom_tuples.

§lex_pairs

use itertools::Itertools;
use malachite_base::tuples::exhaustive::lex_pairs;

assert_eq!(
    lex_pairs('a'..'f', 0..3).collect_vec(),
    &[
        ('a', 0),
        ('a', 1),
        ('a', 2),
        ('b', 0),
        ('b', 1),
        ('b', 2),
        ('c', 0),
        ('c', 1),
        ('c', 2),
        ('d', 0),
        ('d', 1),
        ('d', 2),
        ('e', 0),
        ('e', 1),
        ('e', 2)
    ]
);

§lex_pairs_from_single

use itertools::Itertools;
use malachite_base::tuples::exhaustive::lex_pairs_from_single;

assert_eq!(
    lex_pairs_from_single(0..3).collect_vec(),
    &[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
);

§lex_triples_xyx

use itertools::Itertools;
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::lex_custom_tuples;

fn unwrap_triple<X, Y, Z>((a, b, c): (Option<X>, Option<Y>, Option<Z>)) -> (X, Y, Z) {
    (a.unwrap(), b.unwrap(), c.unwrap())
}

lex_custom_tuples!(
    (pub(crate)),
    LexTriplesXYX,
    (X, Y, X),
    (None, None, None),
    unwrap_triple,
    lex_triples_xyx,
    [X, I, xs, [0, x_0], [2, x_2]],
    [Y, J, ys, [1, y_1]]
);

// We are generating triples of `char`, `i8`, and `char` using two input iterators. The first
// iterator, `xs`, the chars 'a' through 'c', and the second, `ys`, produces the three numbers
// 0, 1, and 2. The function we're using is `lex_triples_xyx`, meaning that the first element of
// the output triples will be taken from `xs`, the second element from `ys`, and the third also
// from `xs`.
let ts = lex_triples_xyx('a'..='c', 0..3);
assert_eq!(
    ts.collect_vec(),
    &[
        ('a', 0, 'a'),
        ('a', 0, 'b'),
        ('a', 0, 'c'),
        ('a', 1, 'a'),
        ('a', 1, 'b'),
        ('a', 1, 'c'),
        ('a', 2, 'a'),
        ('a', 2, 'b'),
        ('a', 2, 'c'),
        ('b', 0, 'a'),
        ('b', 0, 'b'),
        ('b', 0, 'c'),
        ('b', 1, 'a'),
        ('b', 1, 'b'),
        ('b', 1, 'c'),
        ('b', 2, 'a'),
        ('b', 2, 'b'),
        ('b', 2, 'c'),
        ('c', 0, 'a'),
        ('c', 0, 'b'),
        ('c', 0, 'c'),
        ('c', 1, 'a'),
        ('c', 1, 'b'),
        ('c', 1, 'c'),
        ('c', 2, 'a'),
        ('c', 2, 'b'),
        ('c', 2, 'c')
    ]
);

§exhaustive_pairs_from_single

use itertools::Itertools;
use malachite_base::tuples::exhaustive::exhaustive_pairs_from_single;

assert_eq!(
    exhaustive_pairs_from_single(0..4).collect_vec(),
    &[
        (0, 0),
        (0, 1),
        (1, 0),
        (1, 1),
        (0, 2),
        (0, 3),
        (1, 2),
        (1, 3),
        (2, 0),
        (2, 1),
        (3, 0),
        (3, 1),
        (2, 2),
        (2, 3),
        (3, 2),
        (3, 3)
    ]
);

§exhaustive_pairs_1_input

use itertools::Itertools;
use malachite_base::chars::exhaustive::exhaustive_ascii_chars;
use malachite_base::exhaustive_tuples_1_input;
use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::num::arithmetic::traits::CheckedPow;
use malachite_base::num::conversion::traits::{ExactFrom, WrappingFrom};
use malachite_base::num::logic::traits::SignificantBits;
use std::cmp::max;
use std::marker::PhantomData;

exhaustive_tuples_1_input!(
    (pub(crate)),
    ExhaustiveTriples1Input,
    exhaustive_triples_1_input,
    exhaustive_triples_from_single,
    (I::Item, I::Item, I::Item),
    [0, output_type_x],
    [1, output_type_y],
    [2, output_type_z]
);

// We are generating triples of `char`s using one input iterator, which produces all ASCII
// `char`s. The third element has a tiny output type, so it will grow more slowly than the other
// two elements (though it doesn't look that way from the first few tuples).
let ts = exhaustive_triples_1_input(
    exhaustive_ascii_chars(),
    BitDistributorOutputType::normal(1),
    BitDistributorOutputType::normal(1),
    BitDistributorOutputType::tiny(),
);
assert_eq!(
    ts.take(20).collect_vec(),
    &[
        ('a', 'a', 'a'),
        ('a', 'a', 'b'),
        ('a', 'a', 'c'),
        ('a', 'a', 'd'),
        ('a', 'b', 'a'),
        ('a', 'b', 'b'),
        ('a', 'b', 'c'),
        ('a', 'b', 'd'),
        ('a', 'a', 'e'),
        ('a', 'a', 'f'),
        ('a', 'a', 'g'),
        ('a', 'a', 'h'),
        ('a', 'b', 'e'),
        ('a', 'b', 'f'),
        ('a', 'b', 'g'),
        ('a', 'b', 'h'),
        ('b', 'a', 'a'),
        ('b', 'a', 'b'),
        ('b', 'a', 'c'),
        ('b', 'a', 'd')
    ]
);

§exhaustive_pairs

use itertools::Itertools;
use malachite_base::tuples::exhaustive::exhaustive_pairs;

let xss = exhaustive_pairs(['a', 'b', 'c'].iter().cloned(), 0..3).collect_vec();
assert_eq!(
    xss,
    &[('a', 0), ('a', 1), ('b', 0), ('b', 1), ('a', 2), ('b', 2), ('c', 0), ('c', 1), ('c', 2)]
);

§exhaustive_pairs_custom_output

use itertools::Itertools;
use malachite_base::iterators::bit_distributor::BitDistributorOutputType;
use malachite_base::tuples::exhaustive::exhaustive_pairs_custom_output;

let xss = exhaustive_pairs_custom_output(
    ['a', 'b', 'c'].iter().cloned(),
    0..3,
    BitDistributorOutputType::normal(1),
    BitDistributorOutputType::tiny(),
)
.collect_vec();
assert_eq!(
    xss,
    &[('a', 0), ('a', 1), ('a', 2), ('b', 0), ('b', 1), ('b', 2), ('c', 0), ('c', 1), ('c', 2)]
);

§exhaustive_triples_xyx

use itertools::Itertools;
use malachite_base::chars::exhaustive::exhaustive_ascii_chars;
use malachite_base::custom_tuples;
use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::num::conversion::traits::{ExactFrom, WrappingFrom};
use malachite_base::num::logic::traits::SignificantBits;
use std::cmp::max;

#[allow(clippy::missing_const_for_fn)]
fn unwrap_triple<X, Y, Z>((a, b, c): (Option<X>, Option<Y>, Option<Z>)) -> (X, Y, Z) {
    (a.unwrap(), b.unwrap(), c.unwrap())
}

custom_tuples!(
    (pub(crate)),
    ExhaustiveTriplesXYX,
    (X, Y, X),
    (None, None, None),
    unwrap_triple,
    exhaustive_triples_xyx,
    exhaustive_triples_xyx_custom_output,
    [X, I, xs, xs_done, [0, output_type_xs_0], [2, output_type_ys_1]],
    [Y, J, ys, ys_done, [1, output_type_xs_2]]
);

// We are generating triples of `char`, `i8`, and `char` using two input iterators. The first
// iterator, `xs`, produces all ASCII `char`s, and the second, `ys`, produces the three numbers
// 0, 1, and 2. The function we're using is `exhaustive_triples_xyx`, meaning that the first
// element of the output triples will be taken from `xs`, the second element from `ys`, and the
// third also from `xs`.
let ts = exhaustive_triples_xyx(exhaustive_ascii_chars(), 0..3);
assert_eq!(
    ts.take(20).collect_vec(),
    &[
        ('a', 0, 'a'),
        ('a', 0, 'b'),
        ('a', 1, 'a'),
        ('a', 1, 'b'),
        ('b', 0, 'a'),
        ('b', 0, 'b'),
        ('b', 1, 'a'),
        ('b', 1, 'b'),
        ('a', 0, 'c'),
        ('a', 0, 'd'),
        ('a', 1, 'c'),
        ('a', 1, 'd'),
        ('b', 0, 'c'),
        ('b', 0, 'd'),
        ('b', 1, 'c'),
        ('b', 1, 'd'),
        ('a', 2, 'a'),
        ('a', 2, 'b'),
        ('b', 2, 'a'),
        ('b', 2, 'b')
    ]
);

§exhaustive_triples_xyx_custom_output

use itertools::Itertools;
use malachite_base::chars::exhaustive::exhaustive_ascii_chars;
use malachite_base::custom_tuples;
use malachite_base::iterators::bit_distributor::{BitDistributor, BitDistributorOutputType};
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::num::conversion::traits::{ExactFrom, WrappingFrom};
use malachite_base::num::logic::traits::SignificantBits;
use std::cmp::max;

#[allow(clippy::missing_const_for_fn)]
fn unwrap_triple<X, Y, Z>((a, b, c): (Option<X>, Option<Y>, Option<Z>)) -> (X, Y, Z) {
    (a.unwrap(), b.unwrap(), c.unwrap())
}

custom_tuples!(
    (pub(crate)),
    ExhaustiveTriplesXYX,
    (X, Y, X),
    (None, None, None),
    unwrap_triple,
    exhaustive_triples_xyx,
    exhaustive_triples_xyx_custom_output,
    [X, I, xs, xs_done, [0, output_type_xs_0], [2, output_type_ys_1]],
    [Y, J, ys, ys_done, [1, output_type_xs_2]]
);

// We are generating triples of `char`, `i8`, and `char` using two input iterators. The first
// iterator, `xs`, produces all ASCII `char`s, and the second, `ys`, produces the three numbers
// 0, 1, and 2. The function we're using is `exhaustive_triples_xyx_custom_output`, meaning that
// the first element of the output triples will be taken from `xs`, the second element from
// `ys`, and the third also from `xs`.
//
// The third element has a tiny output type, so it will grow more slowly than the other two
// elements (though it doesn't look that way from the first few tuples).
let ts = exhaustive_triples_xyx_custom_output(
    exhaustive_ascii_chars(),
    0..3,
    BitDistributorOutputType::normal(1),
    BitDistributorOutputType::normal(1),
    BitDistributorOutputType::tiny(),
);
assert_eq!(
    ts.take(20).collect_vec(),
    &[
        ('a', 0, 'a'),
        ('a', 0, 'b'),
        ('a', 0, 'c'),
        ('a', 0, 'd'),
        ('a', 1, 'a'),
        ('a', 1, 'b'),
        ('a', 1, 'c'),
        ('a', 1, 'd'),
        ('a', 0, 'e'),
        ('a', 0, 'f'),
        ('a', 0, 'g'),
        ('a', 0, 'h'),
        ('a', 1, 'e'),
        ('a', 1, 'f'),
        ('a', 1, 'g'),
        ('a', 1, 'h'),
        ('b', 0, 'a'),
        ('b', 0, 'b'),
        ('b', 0, 'c'),
        ('b', 0, 'd')
    ]
);

§lex_ordered_unique_quadruples

use itertools::Itertools;
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::lex_ordered_unique_tuples;
use malachite_base::vecs::exhaustive::fixed_length_ordered_unique_indices_helper;
use std::marker::PhantomData;

lex_ordered_unique_tuples!(
    (pub(crate)),
    LexOrderedUniqueQuadruples,
    4,
    (I::Item, I::Item, I::Item, I::Item),
    lex_ordered_unique_quadruples,
    [0, 1, 2, 3]
);

let xss = lex_ordered_unique_quadruples(1..=6).collect_vec();
assert_eq!(
    xss.into_iter().collect_vec().as_slice(),
    &[
        (1, 2, 3, 4),
        (1, 2, 3, 5),
        (1, 2, 3, 6),
        (1, 2, 4, 5),
        (1, 2, 4, 6),
        (1, 2, 5, 6),
        (1, 3, 4, 5),
        (1, 3, 4, 6),
        (1, 3, 5, 6),
        (1, 4, 5, 6),
        (2, 3, 4, 5),
        (2, 3, 4, 6),
        (2, 3, 5, 6),
        (2, 4, 5, 6),
        (3, 4, 5, 6)
    ]
);

§exhaustive_ordered_unique_quadruples

use itertools::Itertools;
use malachite_base::exhaustive_ordered_unique_tuples;
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::vecs::exhaustive::next_bit_pattern;

exhaustive_ordered_unique_tuples!(
    (pub(crate)),
    ExhaustiveOrderedUniqueQuadruples,
    4,
    (I::Item, I::Item, I::Item, I::Item),
    exhaustive_ordered_unique_quadruples,
    [0, 1, 2, 3]
);

let xss = exhaustive_ordered_unique_quadruples(1..=6).collect_vec();
assert_eq!(
    xss.into_iter().collect_vec().as_slice(),
    &[
        (1, 2, 3, 4),
        (1, 2, 3, 5),
        (1, 2, 4, 5),
        (1, 3, 4, 5),
        (2, 3, 4, 5),
        (1, 2, 3, 6),
        (1, 2, 4, 6),
        (1, 3, 4, 6),
        (2, 3, 4, 6),
        (1, 2, 5, 6),
        (1, 3, 5, 6),
        (2, 3, 5, 6),
        (1, 4, 5, 6),
        (2, 4, 5, 6),
        (3, 4, 5, 6)
    ]
);

§lex_unique_quadruples

use itertools::Itertools;
use malachite_base::iterators::iterator_cache::IteratorCache;
use malachite_base::lex_unique_tuples;
use malachite_base::vecs::exhaustive::{unique_indices, UniqueIndices};

lex_unique_tuples!(
    (pub(crate)),
    LexUniqueQuadruples,
    4,
    (I::Item, I::Item, I::Item, I::Item),
    lex_unique_quadruples,
    [0, 1, 2, 3]
);

let xss = lex_unique_quadruples(1..=6).take(20).collect_vec();
assert_eq!(
    xss.into_iter().collect_vec().as_slice(),
    &[
        (1, 2, 3, 4),
        (1, 2, 3, 5),
        (1, 2, 3, 6),
        (1, 2, 4, 3),
        (1, 2, 4, 5),
        (1, 2, 4, 6),
        (1, 2, 5, 3),
        (1, 2, 5, 4),
        (1, 2, 5, 6),
        (1, 2, 6, 3),
        (1, 2, 6, 4),
        (1, 2, 6, 5),
        (1, 3, 2, 4),
        (1, 3, 2, 5),
        (1, 3, 2, 6),
        (1, 3, 4, 2),
        (1, 3, 4, 5),
        (1, 3, 4, 6),
        (1, 3, 5, 2),
        (1, 3, 5, 4)
    ]
);

§exhaustive_unique_quadruples

use itertools::Itertools;
use malachite_base::exhaustive_unique_tuples;
use malachite_base::num::iterators::{ruler_sequence, RulerSequence};
use malachite_base::tuples::exhaustive::{
    exhaustive_dependent_pairs, ExhaustiveDependentPairs,
};
use malachite_base::vecs::exhaustive::{
    exhaustive_ordered_unique_vecs_fixed_length, ExhaustiveOrderedUniqueCollections,
    ExhaustiveUniqueVecsGenerator,
};
use malachite_base::vecs::ExhaustiveVecPermutations;

exhaustive_unique_tuples!(
    (pub(crate)),
    ExhaustiveUniqueQuadruples,
    4,
    (I::Item, I::Item, I::Item, I::Item),
    exhaustive_unique_quadruples,
    [0, 1, 2, 3]
);

let xss = exhaustive_unique_quadruples(1..=6).take(20).collect_vec();
assert_eq!(
    xss.into_iter().collect_vec().as_slice(),
    &[
        (1, 2, 3, 4),
        (1, 2, 3, 5),
        (1, 2, 4, 3),
        (1, 2, 4, 5),
        (1, 3, 2, 4),
        (1, 2, 5, 3),
        (1, 3, 4, 2),
        (1, 3, 4, 5),
        (1, 4, 2, 3),
        (1, 3, 2, 5),
        (1, 4, 3, 2),
        (1, 2, 5, 4),
        (2, 1, 3, 4),
        (1, 3, 5, 2),
        (2, 1, 4, 3),
        (2, 3, 4, 5),
        (2, 3, 1, 4),
        (1, 5, 2, 3),
        (2, 3, 4, 1),
        (1, 4, 2, 5)
    ]
);

Structs§

  • ExhaustiveDependentPairs
    Generates pairs $(x, y)$, where the possible values of $y$ depend on the value of $x$.
  • ExhaustiveOrderedUniquePairs
    This documentation applies not only to ExhaustiveOrderedUniquePairs, but also to ExhaustiveOrderedUniqueTriples, ExhaustiveOrderedUniqueQuadruples, and so on. See exhaustive_ordered_unique_tuples for more information.
  • ExhaustivePairs
    This documentation applies not only to ExhaustivePairs, but also to ExhaustiveTriples, ExhaustiveQuadruples, and so on. See exhaustive_tuples for more information.
  • ExhaustivePairs1Input
    This documentation applies not only to ExhaustivePairs1Input, but also to ExhaustiveTriples1Input, ExhaustiveQuadruples1Input, and so on. See exhaustive_tuples_1_input for more information.
  • ExhaustiveUniquePairs
    Generates all pairs of elements from an iterator, where the pairs have no repetitions.
  • LexDependentPairs
    Generates pairs $(x, y)$, where the possible values of $y$ depend on the value of $x$. All $y$ values are output before proceeding to the next $x$.
  • LexOrderedUniquePairs
    This documentation applies not only to LexOrderedUniquePairs, but also to LexOrderedUniqueTriples, LexOrderedUniqueQuadruples, and so on. See lex_ordered_unique_tuples for more information.
  • LexPairs
    This documentation applies not only to LexPairs, but also to LexTriples, LexQuadruples, and so on. See lex_tuples for more information.
  • LexPairsFromSingle
    This documentation applies not only to LexPairsFromSingle, but also to LexTriplesFromSingle, LexQuadruplesFromSingle, and so on. See lex_tuples for more information.
  • LexUniquePairs
    This documentation applies not only to LexUniquePairs, but also to LexUniqueTriples, LexUniqueQuadruples, and so on. See lex_unique_tuples for more information.

Traits§

Functions§