rustコンビネーションアルゴリズム

.rust合成アルゴリズム

簡単な説明

コード

次の組み合わせ番号

を計算します.

mmmm

は、すべての組み合わせの中で最大と

を求めます.
rustコンビネーションアルゴリズム
簡単に述べる
組み合わせ:mの長い数列を求めて、n(n)<=m)の要素のすべての組み合わせ.
コード
次のグループ番号を計算します.

fn generate_next_index(length :usize,index:&mut Vec){
    let index_length = index.len();
    let mut p:usize = index_length-1;
    loop {
        if p < 1{
                break;
            }
        if index[p]  == length+p-index_length{
            p -= 1;
        }else{
            break;
        }
    }
    let mut num:usize;
    num = index[p];
    while p< index_length{
        num +=1;
        index[p] = num;
        p+=1;
    }
}

ミリ

fn print_all_c(ls :&Vec<i64>,n usize){
    let length = ls.len();
    if n > length{
        return
    }
    let mut index:Vec = (0..n as usize).collect();
    let last_index = ls.len() - k as usize;
    let mut start_index:usize = 0;
    while start_index <= last_index{
        index.iter().for_each(|&x| print!("{} ",ls[x]));
        print!("
")
        generate_next_index(length,&mut index);
        start_index = index[0];
    }
}

すべての組み合わせの中の最大の和を求めます.

fn get_max_sum(ls:&Vec<i64>,n usize) -> i64{
    let mut res:i64 = -1;
    let length = ls.len();
    if n > length{
        return res;
    }
    let mut index:Vec = (0..n as usize).collect();
    let last_index = ls.len() - k as usize;
    let mut start_index:usize = 0;
    let mut sum:i64;
    while start_index <= last_index{
        sum = index.iter().fold(0,|ass,&x| ass+ls[x]);
        if sum > res{
            res = sum;
        }
        generate_next_index(length,&mut index);
        start_index = index[0];
    }
}

ps:rust Iiteratorは、pythonにおけるfoldと同様の方法を提供する.