CODEWITHSUNDEEP
rust
Enum
Enum

Reputation: 184

Get all combinations of a vector of n-chars

For a vector of n-chars, I'd like to get all possible combinations these chars can form.

let characters = vec!["a", "b"];

The expected 2² output would be: ["aa", "ab", "bb", "ba"]

combinations_with_replacement(2) does not account for the inversed ["ba"] case and permutations(2) does not include combinations of values of itself ["aa", "bb"].

Am I overlooking something in itertools::Itertools or is there simply no straight forward way to do this?

Upvotes: 1

Views: 3665

Answers (1)

harmic
harmic

Reputation: 30597

For a simple case like this you probably don't need any crates:

    let characters = vec!["a", "b"];
    let combinations : Vec<_> = characters.iter()
        .map(|&c| characters.iter().map(move |&d| d.to_owned() + c))
        .flatten()
        .collect();

Playground

As pointed out in the comments, this solution is limited to a number of combinations known at compile time. If you need to a number of combinations which is only known at runtime, you could use this:

    let characters = vec!["a", "b"];

    let n=4; // The number of combinations
    
    let combinations : Vec<_> = (2..n).fold(
        characters.iter().map(|c| characters.iter().map(move |&d| d.to_owned() + *c)).flatten().collect(),
        |acc,_| acc.into_iter().map(|c| characters.iter().map(move |&d| d.to_owned() + &*c)).flatten().collect()
    );

Playground

If you did want to use itertools, as @kmdreko points out you would be using cartesian_product:

use itertools::Itertools;

fn main() {
    let characters = vec!["a", "b"];
    let combinations : Vec<_> = characters.iter()
        .cartesian_product(characters.iter())
        .map(|(&a, &b)| a.to_owned() + b)
        .collect();
    println!("{:?}", combinations);
}

Playground

Note in the above solution that cartesian_product returns a tuple - so to obtain a string containing the combinations, we need to map the result.

Finally, if you want to use cartesian_product and you need a number of combinations known only at runtime:

use itertools::Itertools;

fn main() {
    let characters = vec!["a", "b"];
    let n = 4;
    
    let combinations : Vec<_> = (2..n).fold(
        characters.iter().cartesian_product(characters.iter()).map(|(&a, &b)| a.to_owned() + b).collect(),
        |acc, _| acc.into_iter().cartesian_product(characters.iter()).map(|(a, b)| a.to_owned() + b).collect()
    );
    println!("{:?}", combinations);
}

Playground

Upvotes: 4

Related Questions