In Rust, I am trying to obtain all possible combinations of a-z characters up to a fixed length with no repeating letters.

For example, for a limited set of a-f and a length of 3 I should get:

abc abd abe abf acb acd ace acf adb ... etc

I've been struggling to do this through recursion and have been banging my head on ownership and borrows. The only way I've managed to do it is as follows, but this is cloning strings all over the place and is very inefficient. There are probably standard permutation/combination functions for this in the standard library, I don't know, but I'm interested in understanding how this can be done manually.

fn main() {
    run(&String::new());
}

fn run(target: &String) {
    for a in 97..123 { // ASCII a..z
        if !target.contains(char::from(a)) {
            let next = target.clone()   char::from(a).to_string().as_str(); // Working but terrible
            if next.len() == 3 { // Required string size
                println!("{}", next);
            } else {
                run(&next);
            }
        }
    }
}

CodePudding user response：

First off, a couple of remarks:

• &String is kind of an anti-pattern that is rarely seen. It serves no purpose; all the functionality that String has over str requires mutability. So it should either be &mut String or &str.
• 97..123 is uncommon ... use 'a'..='z'.

Now to the actual problem:

As long as you pass a non-mutable string into the recursion, you won't get around cloning the data. I'd make the string mutable, then you can simply append and remove single characters from it.

Like this:

fn main() {
    run(&mut String::new());
}

fn run(target: &mut String) {
    for a in 'a'..='z' {
        if !target.contains(a) {
            target.push(a);
            if target.len() == 3 {
                // Required string size
                println!("{}", target);
            } else {
                run(target);
            }
            target.pop();
        }
    }
}

CodePudding user response：

Here is another way to do it, using itertools.

It's probably cleaner to return the String object from the function directly.

use std::ops::RangeInclusive;
use itertools::Itertools;

fn main() {
    println!("result: {}",combine('a'..='d', 3));
    println!("result: {}",combine('a'..='g', 4));
    println!("result: {}",combine('a'..='c', 3));
    println!("result: {}",combine('a'..='c', 4)); // assertion fail
}

fn combine(range: RangeInclusive<char>, depth: usize) -> String
{
    assert!( *range.end() as usize - *range.start() as usize   1 >= depth);

    let perms = range.permutations(depth);
    let mut result = String::new();

    perms.for_each(|mut item| {
        item.push(' ');
        result  = &item.into_iter().collect::<String>();
    });
    result.pop(); // pop last superfluous space char
    result
}