Finding possible combinations for n<7 with rust

Question

I am trying to learn rust and as such have been redoing some of the challenges on project Rosalind. This one relates to the challenge Enumerating Gene Orders.

fn all_combinations(mut combinations: Vec<Vec<usize>>, chain: Vec<usize>, mut choices: Vec<usize>, max: usize) -> Vec<Vec<usize>>{

    // filling options
    if choices.len() == 0 {
        choices = (1..max+1).collect();
    }
    
    // loop over all potential numbers and appending the chain
    for (i, numb) in choices.iter().enumerate(){

        let mut local_chain: Vec<usize> = chain.clone();            

        local_chain.push(*numb);

        // remove used number by its index
        let reduced_choices: Vec<usize> = [&choices[..i], &choices[i+1..]].concat();
        
        // nothing more to add
        if reduced_choices.len() == 0 {         
            combinations.push(local_chain); 
            return combinations;
        }

        // depth still left
        else{
            combinations = all_combinations(combinations.clone(), local_chain, reduced_choices, max);
        }   
    }
    
    combinations
}

Above is called as such:

let combinations: Vec<Vec<usize>> = Vec::new();
let chain: Vec<usize> = Vec::new();
let choices: Vec<usize> = Vec::new();

let all_combinations = all_combinations(combinations, chain, choices, 5);

I know that for n > 8 with this algorithm it going to take an infinite amount of time to finish, but I'm really interested in how incorrect my code snippet is in terms of Rust guidelines and good practices since many things are still quite alien to me.

Thanks

before any Rust comment, you don't need any vec to do that, first find a better algo — Stargateur
– Stargateur, Commented Nov 7, 2021 at 19:46

M. Maraist · Accepted Answer · 2021-11-24 18:55:17Z

As already stated, not sure why you're returning vectors; the linked question asks for a number. And with that, you can use big-integers with simple calculations; some already do num-combin and num-perm efficiently behind the scenes.

Ignoring the algorithm though (since that seems to be your intent), you're passing ownership of values that you're not modifying. In most cases you should accept a reference. Specifically "chain: &Vec<u8>"

It's debatable whether accepting a mutable vector (the combinations) as owned, then returning it when you're done is a good practice. It's technically fine. But more generally that's a mutable borrow "combinations: &mut Vec<Vec<u8>>" with no return value then.

Instead of declaring a mutable input parameter just to affect the default, you should accept it as immutable and conditinoally initialize a local. Change 'mut choices: Vec<usize>' to '_choices: &Vec<u8>' then in the code use 'let choices = if _choices.len() > 0 { _choices } else { ... }; . It avoids losing ownership by the caller (in general you shouldn't take ownership unless you need it)

Notice also, the usize is 4 or 8 bytes; usize is meant for vector-lengths and pointers (e.g. machine pointer sizes). Whereas u8,u16,u32,u64,u128 are meant for math. So if your max is bounded (since you'd run out of memory), you might as well use capped types; rust will assert that you do not exceed the max value. u8 would work in your example, but for this class of problem, u32 might be decent.. The main point is usize is unknown/platform specific, so not appropriate here.

Next Vec<Vec<u8>> feels akward to me you're returning a fixed length tuplet; rather all second dimension fields are the same length. Let There is a 24 byte overhead in each of the second dimension fields.. You have a pointer-struct to-a pointer-struct. It's less efficient than a C double array.

fn all_combinations<N:usize>(..) -> Vec<[u8 ; N]> {}

would be slightly better, as the inner array is a fixed-length struct. Though it means N is no longer a variable; it's not a compile-time constant.

Not sure the best way to do a 2D array in rust actually; I typically do 1D arrays with manual offset calculations (in other languages like java, where 2D is more expensive, just like here). So replacing combinations:Vec<Vec<u8>> with combinations:Vec<u8> but using slices of size N.

The concatenated arrays also irks me the wrong way.. It's certainly functional, so Lisp would love it. But that's pretty damn expensive here. Would be better to have a temp Vector, clear it between each iteration, then copy slices onto it. You could then copy the final slices into a fixed range offset of the 1D output array (from previous section).

Not crazy about iterating over the choices vector. The consequence here is that you have an if-return in the middle of your loop.. Ideally you have a single return point. If you just did a let mut i = 0; while !reduced_choices.is_empty() { let numb=choices[i]; ... i += 1; } that would be slightly cleaner to my eye. Would also happen to get rid of the ugly '*numb'

Stack Exchange Network

Finding possible combinations for n<7 with rust

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Finding possible combinations for n<7 with rust

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions