Skip to content

Instantly share code, notes, and snippets.

@danlucraft
Last active August 29, 2015 14:07
Show Gist options
  • Save danlucraft/562041c8e0c3add6199e to your computer and use it in GitHub Desktop.
Save danlucraft/562041c8e0c3add6199e to your computer and use it in GitHub Desktop.
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));
}
}
$ ./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]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment