Creating a generator for enumerating things

Suppose n and d are natural numbers. For some reason, I wish to enumerate all pairs (S, R) where S is a Vec<bool> of length exactly n, and R is a Vec<Vec<Vec<bool>>> of size exactly d consisting of square matrices of size exactly n * n (i.e, binary relations on n elements). Thus, I want something of type Iterator<Item=(Vec<bool>, Vec<Vec<Vec<bool>>>)>.

How do I create such an iterator that iterates through each of these objects on demand, i.e, not precompute them?

For analogy, here is how I would do this in Haskell:

type Subset = [Bool]
type Relation = [[Bool]] -- a square matrix

allSubsets :: Int -> [Subset]
allSubsets n = sequence $ replicate n [True, False]

-- all Relations between a subset of n elements and a subset of m elements
allRelations :: Int -> Int -> [Relation]
allRelations n m = sequence $ replicate n (allSubsets m)

-- all families of d relations on a set of n elements
enumerateTransitions :: Int -> Int -> [[Relation]]
enumerateTransitions n d = sequence $ replicate d (allRelations n n)

-- all possible pairs of (a subset of n elements, along with d relations on them)
enumerate :: Int -> Int -> [(Subset, [Relation])]
enumerate n d = do
    finalStates <- allSubsets n
    transs <- enumerateTransitions n d
    pure (finalStates, transs)

Here's one way (assuming I understood the specification correctly):

use itertools::Itertools; // provides .multi_cartesian_product()

pub fn many<I, T>(n: usize, i: I) -> impl Iterator<Item = Vec<T>> + Clone
where
    I: IntoIterator<Item = T>,
    I::IntoIter: Clone,
    T: Clone,
{
    let i = i.into_iter();
    (0..n).map(|_| i.clone()).multi_cartesian_product()
}

pub fn things(d: usize, n: usize) -> impl Iterator<Item = (Vec<bool>, Vec<Vec<Vec<bool>>>)> {
    let n_bools = many(n, [false, true]);
    let nn_bools = many(n, n_bools.clone());
    let nnd_bools = many(d, nn_bools);
    n_bools.cartesian_product(nnd_bools)
}

#[test]
fn test() {
    let r = things(2, 1).collect::<Vec<_>>();
    for x in r.iter() {
        println!("{x:?}");
    }
    assert_eq!(
        r,
        vec![
            (vec![false], vec![vec![vec![false]], vec![vec![false]]]),
            (vec![false], vec![vec![vec![false]], vec![vec![true]]]),
            (vec![false], vec![vec![vec![true]], vec![vec![false]]]),
            (vec![false], vec![vec![vec![true]], vec![vec![true]]]),
            (vec![true], vec![vec![vec![false]], vec![vec![false]]]),
            (vec![true], vec![vec![vec![false]], vec![vec![true]]]),
            (vec![true], vec![vec![vec![true]], vec![vec![false]]]),
            (vec![true], vec![vec![vec![true]], vec![vec![true]]]),
        ]
    )
}
1 Like

Thanks! That looks great. I did not know about multi_cartesian_product

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.