Enumerate permutations with repetitions for lengths 1 to `n`

help
1

I've been looking at some of my past code and recently rediscovered this:

// Enumerate all permutations with repetitions and for all output lengths from 1 to `max_len`.
// Don't ask me how this works, I typed it out in a single stream of consciousness.
fn perms_iter<'a, T: Copy>(
	input: &'a [T],
	max_len: u32,
) -> impl Iterator<Item = impl Iterator<Item = T> + 'a> {
	(1..=max_len)
		.flat_map(move |len| (0..input.len().pow(len)).zip(std::iter::repeat(len)))
		.map(move |(mut n, j)| {
			(0..j).map(move |_| {
				let s = input[n % input.len()];
				n /= input.len();
				s
			})
		})
}

I need something similar now but past me's comment isn't very encouraging. Can this be done better?

EDIT: It's used like this:

for perm in perms_iter(&['a', 'b', 'c'], 4) {
    for c in perm {
        print!("{}", c);
    }
    println!("");
}

Playground link.

2

I like how you’re encoding the items as numbers in base j/len.

I’m not sure what you’re after in terms of “better”. And what is this “something similar” that you’re tackling now?

1 Like
3

I guess, changing pow to checked_pow+unwrap could be an improvement, if you’re planning on ever risking an overflow, otherwise some items very late in the iterator may be messed up on 32bit platforms in release mode.

1 Like
4

That is certainly a valid approach. Just beware of integer division performance.

itertools has your function too: itertools::Itertools - Rust

I would probably try to write it using arrays to avoid the allocations and generate the iterator with a macro to avoid integer division. (but a branch misprediction is probably more costly .. so yours might still be faster).

1 Like
5

Not really the same, that one’s producing Vectors. And it’s actually doing only permutations, whereas the one here is more of a cartesian products thing.

6

Well I was looking to generate an exhaustive (up to n chars) test of a simple parser and this looked like it might do the job but the comment I left myself had me worried (but maybe I was just feeling unhelpful that day).

I would like something that I can plug right into rayon but if the code is basically ok then I can adapt it.

7

The code here doesn’t cover the case of length 0 though…

8

True! But I have that case covered.

9

turns out, changing (1..=max_len) to (0..=max_len) works fine, too ^^

1 Like
10

I guess, if you like, you can avoid the zip by pulling the .map inside of the flat_map

fn perms_iter<'a, T: Copy>(
    input: &'a [T],
    max_len: u32,
) -> impl Iterator<Item = impl Iterator<Item = T> + 'a> {
    (0..=max_len).flat_map(move |len| {
        (0..input.len().pow(len)).map(move |mut n| {
            (0..len).map(move |_| {
                let s = input[n % input.len()];
                n /= input.len();
                s
            })
        })
    })
}
11

Ah, I actually find that a bit more readable. Thanks!

12

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.