Permutations with replacement in rust?

Question

I'd like to write a generic function that can make all unique vectors where each index has a series of values.

Easiest to illustrate with an example.

for i in (1..3).combinations_with_replacement(3) {
   println!("{:?}",i);
}

Produces the ouput

[1, 1, 1]
[1, 1, 2]
[1, 2, 2]
[2, 2, 2]

Which is not satisfactory because it's missing members like

[1, 2, 1]
[2, 1, 2]
[2, 2, 1]

So I also tried permutations(3) but since their are more positions than items in the iterator, the iterator is empty. There also doesn't appear to be a permutations_with_replacement but maybe that'd be the name of the function I'm looking for.

In this case you could accomplish the task with 3 nested for loops but this is ugly and not a general solution. I think a recursive backtracking solution could do it too but seems like their should be something in itertools that I'm missing.

---

Here's another example of what I want but with code written a few languages that aren't rust.

Answer 1

Using itertools, based on @Ry-'s suggestion:

for i in (1..=3).map(|_| 1..=2).multi_cartesian_product()  {
   println!("{i:?}");
}

Output:

[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[2, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 2, 2]

Playground

Answer 2

I'm not sure how this can be done using itertools, but here is one way to achieve the same result in plain Rust.

pub struct PermutationsReplacementIter<I> {
    items: Vec<I>,
    permutation: Vec<usize>,
    group_len: usize,
    finished: bool,
}

impl<I: Copy> PermutationsReplacementIter<I> {
    fn increment_permutation(&mut self) -> bool {
        let mut idx = 0;

        loop {
            if idx >= self.permutation.len() {
                return true;
            }

            self.permutation[idx] += 1;

            if self.permutation[idx] >= self.items.len() {
                self.permutation[idx] = 0;
                idx += 1;
            } else {
                return false;
            }
        }
    }

    fn build_vec(&self) -> Vec<I> {
        let mut vec = Vec::with_capacity(self.group_len);

        for idx in &self.permutation {
            vec.push(self.items[*idx]);
        }

        vec
    }
}

impl<I: Copy> Iterator for PermutationsReplacementIter<I> {
    type Item = Vec<I>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.finished {
            return None;
        }

        let item = self.build_vec();

        if self.increment_permutation() {
            self.finished = true;
        }

        Some(item)
    }
}

pub trait ToPermutationsWithReplacement {
    type Iter;
    fn permutations_with_replacement(self, group_len: usize) -> Self::Iter;
}

impl<I: Iterator> ToPermutationsWithReplacement for I {
    type Iter = PermutationsReplacementIter<<I as Iterator>::Item>;

    fn permutations_with_replacement(self, group_len: usize) -> Self::Iter {
        let items = self.collect::<Vec<_>>();
        PermutationsReplacementIter {
            permutation: vec![0; group_len],
            group_len,
            finished: group_len == 0 || items.len() == 0,
            items,
        }
    }
}

Then it can be used similarly to combinations_with_replacement.

for x in (1..3).permutations_with_replacement(3) {
    println!("{:?}", x);
}

// Output:
[1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[2, 2, 1]
[1, 1, 2]
[2, 1, 2]
[1, 2, 2]
[2, 2, 2]

Playground Link

You can also put it on any iterator where the elements implement Copy. However, I wouldn't recommend it. The time complexity for this task is extremely bad. For an input iterator of n elements in groups of length m, this will create an iterator of about n^m items assuming my math is correct.