# 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.