ordered_permutation/
lib.rs

1// check that results are unique
2#[cfg(test)]
3#[test]
4fn unique() {
5	let a = permutate(&vec![1,2,3,4,5]);
6
7	let mut b: Vec<Vec<u8>> = vec![];
8
9	for v in a.iter() {
10		assert!(!b.contains(&v));
11		b.push(v.clone());
12	}
13
14	// ok
15}
16
17#[test]
18fn count() {
19	let a = permutate(&[1,2]);
20	println!("{}", a.len() == 3);
21
22	let a = permutate(&[1,2,3]);
23	println!("{}", a.len() == 7 );
24
25	let a = permutate(&vec![1,2,3,4]);
26	println!("{}", a.len() == 15);
27
28	let a = permutate(&vec![1,2,3,4,5]);
29	println!("{}", a.len() == 31);
30
31	let a = permutate(&vec![1,2,3,4,5,6]);
32	println!("{}", a.len() == 63);
33
34	// ok
35}
36
37pub fn permutate(source: &[u8]) -> Vec<Vec<u8>> {
38	let mut root = Node::new(vec![]);
39	for val in source.iter() {
40		root.insert(*val);
41	}
42	
43	root.extract()
44}
45
46struct Node {
47    nums: Vec<u8>,
48    children: Vec<Node>
49}
50
51impl Node {
52    fn new(nums: Vec<u8>) -> Node {
53        Node{nums: nums, children: vec![]}
54    }
55
56    fn insert(&mut self, num: u8) {
57        if self.nums.len() == 0 || self.nums[self.nums.len()-1] < num {
58
59		let mut v = vec![];
60		v.extend(&self.nums);
61		v.push(num);
62            self.children.push(Node::new(v));
63
64            for mut node in self.children.iter_mut() {
65                node.insert(num);
66            }
67        }
68    }
69
70    fn extract(&self) -> Vec<Vec<u8>> {
71		let mut v: Vec<Vec<u8>> = vec![];
72		if self.nums.len() > 0 {
73			v.push(self.nums.clone());
74		}
75		for node in self.children.iter() {
76			v.extend(node.extract());
77		}
78		v
79    }
80}
81
ordered_permutation/lib.rs

ordered_permutation/
lib.rs
