Please consider a simple recursive function below to generate permutations of single characters in a string such as "ABCD" (which generates 4!=24 permutations).
This fn works fine but as avid Rust learner I would like to make it into Iterator so I can use next() method and Rust for loops and all other wonderful Rust iterator features.
My Question:
what is the most Rust idiomatic (and performant) way to convert this recursive fn to work ar Rust Iterator?
I understand that Rust 1.72 stable does not have a "Yield" functionality.
So perhaps there is another way to do it in Rust 1.72 ?
PS I am aware the itertools crate has the "permutations" functionality already.
I am asking this question in order to help me learn Rust.
thank you very much
// gen_str2(p, "ABCD");
fn gen_str2(perm: String, word: &str) {
if word.len() == 0 {
println!("result:{perm}");
} else {
for i in 0..word.len() {
let mut perm2 = perm.clone();
perm2.push(word.chars().nth(i).unwrap());
gen_str2(perm2, format!("{}{}", &word[0..i], &word[i + 1..]).as_str());
}
}
}
fn main() {
let p = String::new();
gen_str2(p, "ABCD");
}
The usual high-level idea behind converting recursion to iteration is to make the stack explicit. Instead of using the call stack of recursive calls, you make a Vec and push onto/pop from it.
fn main() {
for s in gen_str3(String::new(), "ABCD") {
println!("{s}");
}
}
fn gen_str3(perm: String, word: &str) -> impl Iterator<Item = String> {
let mut perms = Vec::new();
if word.is_empty() {
perms.push(perm);
} else {
for (i, c) in word.char_indices() {
let perm2 = format!("{perm}{c}");
let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
perms.extend(gen_str3(perm2, &word2));
}
}
perms.into_iter()
}
This will let you test your iterator against something you know is correct. I've also changed this to use char_indices so that it's correct for multi-byte characters.
Then you need to recreate the stack. This means saving all values that are present whenever you make the recursive call. If I did this completely, I would have to include the for loop iterator in the stack and recreate the for loop logic, and you may need to do that for more complex recursive functions, but I've taken a shortcut and kept the for loop for simplicity. The downside of this is if you cancel the iterator early, a few strings will be created and never used. (playground)
fn gen_str4(perm: String, word: &str) -> impl Iterator<Item = String> {
let mut stack = vec![(perm, word.to_string())];
// This closure returns Some(None) when no value is ready yet, but the iterator should
// continue. It returns Some(Some(_)) when a value is ready. And it returns None when
// the iterator is done.
std::iter::from_fn(move || -> Option<Option<String>> {
// When the stack is empty, end the iterator
let (perm, word) = stack.pop()?;
// All characters are used up, return the permutation
if word.is_empty() {
return Some(Some(perm));
}
// Make bigger perms and add them to the stack
// Reverse to match the recursive version
for (i, c) in word.char_indices().rev() {
let perm2 = format!("{perm}{c}");
let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
stack.push((perm2, word2));
}
Some(None)
})
// Flatten to convert the item type from Option<String> to String
.flatten()
}
Also, the pattern of writing sequential code and transforming it into an iterator is accomplished by generators. Unfortunately however Rust doesn't support stable generators yet. Moreover generators don't really like recursion, you would have to Box the recursive calls, effectively replacing the call stack with a linked list.
It creates all the values before even the first item is returned. This means it has all N! values in memory at once, whereas the other ones have at most N^2 values in memory at once.
Here's the correct generator version for the future (playground)
fn gen_str5(perm: String, word: String) -> impl Iterator<Item = String> {
let gen = move || {
if word.is_empty() {
yield perm;
} else {
let mut i = 0;
while i < word.len() {
let c = word[i..].chars().next().unwrap();
let perm2 = format!("{perm}{c}");
let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
for perm in gen_str5(perm2, word2) {
yield perm;
}
i += c.len_utf8();
}
}
};
Box::new(std::iter::from_generator(gen)) as Box<dyn Iterator<Item = String>>
}
It needs to take String and use a while loop since you can't hold references across a yield, and it needs to be boxed because it's recursive. But other than that, it's pretty solid and matches the recursive version.
Because it's useless: it generates all elements eagerly, meanwhile the whole point of the iterator abstraction is to avoid doing that. So if you generate everything upfront anyway in a dynamic array, then there's no point to hide it behind an iterator, so that's bad style.