choose.rs

choose.rs

use std::os;

fn choose_k<'r, T>(arr: &[&'r T], k: uint) -> Vec<Vec<&'r T>> {
    if k > arr.len() {
        vec![]
    } else if k == 0 {
        vec![vec![]]
    } else {
        let mut result: Vec<Vec<&T>> = choose_k(arr.slice(1, arr.len()), k - 1).into_iter().map(|v| { 
            let mut x = vec![arr[0]];
            x.push_all(v.as_slice());
            x 
        }).collect();
        result.push_all(choose_k(arr.slice(1, arr.len()), k).as_slice());
        result
    }
}


fn main() {
    let ref s = os::args()[1];
    let val = s.as_slice();
    let x: uint = from_str(val).unwrap();
    
    let r = range(1u, x + 1).collect::<Vec<uint>>();
    let list = r.iter().collect::<Vec<&uint>>();
    let list1 = list.as_slice();
    
    for i in range(0u, x + 1) {
        println!("{} from {}: {}", i, list1, choose_k(list1, i));
    }
}

output

$ ./choose 5
0 from [1, 2, 3, 4, 5]: [[]]
1 from [1, 2, 3, 4, 5]: [[1], [2], [3], [4], [5]]
2 from [1, 2, 3, 4, 5]: [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]
3 from [1, 2, 3, 4, 5]: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
4 from [1, 2, 3, 4, 5]: [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
5 from [1, 2, 3, 4, 5]: [[1, 2, 3, 4, 5]]