discrete/
permutation.rs

1
2use std::marker::PhantomData;
3use std::ops::{
4    AddAssign,
5    MulAssign,
6    Sub,
7    Mul,
8    SubAssign,
9    DivAssign,
10    Div,
11};
12use std::convert::TryInto;
13use std::fmt::Debug;
14
15use num::BigUint;
16
17use Construct;
18use Data;
19use Of;
20use space::Space;
21
22/// Dimension is natural number, position is a list of numbers.
23pub struct Permutation<T = Data>(PhantomData<T>);
24
25impl<T> Construct for Permutation<T> {
26    fn new() -> Self { Permutation(PhantomData) }
27}
28
29impl Space<usize> for Permutation<Data> {
30    type Dim = usize;
31    type Pos = Vec<usize>;
32    fn count(&self, dim: &usize) -> usize {
33        let mut res = 1;
34        for x in 1..dim + 1 {
35            res *= x;
36        }
37        res
38    }
39    fn zero(&self, dim: &usize) -> Vec<usize> {
40        vec![0; *dim]
41    }
42    fn to_index(&self, dim: &usize, pos: &Vec<usize>) -> usize {
43        let mut index = 0;
44        let mut count = 1;
45        for (i, &x) in pos.iter().enumerate().rev() {
46            let lower = pos[..i].iter().filter(|&&y| y < x).count();
47            index += count * (x - lower);
48            count *= dim - i;
49        }
50        index
51    }
52    fn to_pos(&self, dim: &usize, mut index: usize, pos: &mut Vec<usize>) {
53        unsafe { pos.set_len(0); }
54
55        let mut count = 1;
56        for (j, x) in (1..dim + 1).enumerate() {
57            count *= x;
58            pos.push(j);
59        }
60
61        for i in 0..*dim {
62            let block = count / (dim - i);
63            let ind = index / block;
64            let item = pos.remove(ind);
65            pos.push(item);
66            count /= dim - i;
67            index -= ind * block;
68        }
69    }
70}
71
72impl Space<BigUint> for Permutation<Data> {
73    type Dim = BigUint;
74    type Pos = Vec<BigUint>;
75    fn count(&self, dim: &BigUint) -> BigUint {
76        let _1: BigUint = 1usize.into();
77        let mut res: BigUint = _1.clone();
78        let mut x = _1.clone();
79        loop {
80            if &x > dim {break}
81            res *= &x;
82            x += &_1;
83        }
84        res
85    }
86    fn zero(&self, dim: &BigUint) -> Vec<BigUint> {
87        let dim: usize = dim.try_into().unwrap();
88        vec![0usize.into(); dim]
89    }
90    fn to_index(&self, dim: &Self::Dim, pos: &Self::Pos) -> BigUint {
91        let mut index: BigUint = 0usize.into();
92        let mut count: BigUint = 1usize.into();
93        for (i, x) in pos.iter().enumerate().rev() {
94            let lower = pos[..i].iter().filter(|&y| y < x).count();
95            index += &count * (x - lower);
96            count *= dim - i;
97        }
98        index
99    }
100    fn to_pos(&self, dim: &Self::Dim, mut index: BigUint, pos: &mut Self::Pos) {
101        pos.clear();
102
103        let mut count: BigUint = 1usize.into();
104        let dim: usize = dim.try_into().unwrap();
105        for (j, x) in (1usize..dim + 1).enumerate() {
106            count *= x;
107            pos.push(j.into());
108        }
109
110        let dim: usize = dim.try_into().unwrap();
111        for i in 0..dim {
112            let block = &count / (dim - i);
113            let ind: BigUint = &index / &block;
114            let item = pos.remove((&ind).try_into().unwrap());
115            pos.push(item);
116            count /= dim - i;
117            index -= &ind * block;
118        }
119    }
120}
121
122impl<N, T> Space<N> for Permutation<Of<T>>
123    where T: Space<N>,
124          T::Pos: Clone,
125          N: Clone +
126             From<usize> +
127             TryInto<usize> +
128             for<'a> AddAssign<&'a N> +
129             for<'a> MulAssign<&'a N> +
130             Sub<usize, Output = N> +
131             SubAssign +
132             DivAssign<usize> +
133             MulAssign<usize> +
134             PartialOrd,
135          <N as TryInto<usize>>::Error: Debug,
136          for<'a> &'a N: Sub<usize, Output = N> +
137                         Mul<&'a N, Output = N> +
138                         Div<usize, Output = N> +
139                         Div<&'a N, Output = N> +,
140          <N as TryInto<usize>>::Error: Debug,
141{
142    type Dim = T::Dim;
143    type Pos = Vec<T::Pos>;
144    fn count(&self, dim: &Self::Dim) -> N {
145        let of: T = Construct::new();
146        let _1: N = 1usize.into();
147        let mut x = _1.clone();
148        let mut res = _1.clone();
149        let of_count = of.count(dim);
150        loop {
151            if &x > &of_count {break}
152            res *= &x;
153            x += &_1;
154        }
155        res
156    }
157    fn zero(&self, dim: &Self::Dim) -> Self::Pos {
158        let of: T = Construct::new();
159        let count = match of.count(dim).try_into() {
160            Ok(x) => x,
161            Err(_) => panic!("Out of range"),
162        };
163        vec![of.zero(dim); count]
164    }
165    fn to_index(&self, dim: &Self::Dim, pos: &Self::Pos) -> N {
166        let of: T = Construct::new();
167        let mut index: N = 0usize.into();
168        let dim_count = of.count(dim);
169        let mut count: N = 1usize.into();
170        for (i, x) in pos.iter()
171            .map(|x| of.to_index(dim, x))
172            .enumerate().rev() {
173            let lower = pos[..i].iter()
174                .map(|y| of.to_index(dim, y))
175                .filter(|y| y < &x).count();
176            index += &(&count * &(x - lower));
177            count *= &(&dim_count - i);
178        }
179        index
180    }
181    fn to_pos(&self, dim: &Self::Dim, mut index: N, pos: &mut Self::Pos) {
182        let of: T = Construct::new();
183        let of_count: usize = of.count(dim).try_into().unwrap();
184        pos.clear();
185
186        let mut count: N = 1usize.into();
187        for (j, x) in (1..of_count + 1).enumerate() {
188            count *= x;
189            let mut new_pos: T::Pos = of.zero(&dim);
190            of.to_pos(dim, j.into(), &mut new_pos);
191            pos.push(new_pos);
192        }
193
194        for i in 0..of_count {
195            let diff = of_count - i;
196            let block = &count / diff;
197            let ind = &index / &block;
198            index -= &ind * &block;
199            let item = pos.remove(ind.try_into().unwrap());
200            pos.push(item);
201            count /= diff;
202        }
203    }
204}
205
206#[cfg(test)]
207mod test {
208    use super::super::*;
209
210    #[test]
211    fn features() {
212        is_complete::<usize, Permutation>();
213        is_complete::<usize, Permutation<Of<Pair>>>();
214    }
215
216    #[test]
217    fn data() {
218        let permutation: Permutation = Construct::new();
219        assert_eq!(permutation.count(&1), 1);
220        assert_eq!(permutation.count(&2), 2);
221        assert_eq!(permutation.count(&3), 6);
222        assert_eq!(permutation.count(&4), 24);
223
224        let mut pos = Vec::new();
225        let ref dim = 4;
226        let count = permutation.count(dim);
227        for i in 0..count {
228            permutation.to_pos(dim, i, &mut pos);
229            let index = permutation.to_index(dim, &pos);
230            assert_eq!(index, i);
231        }
232    }
233
234    #[test]
235    fn data_big() {
236        use std::convert::TryInto;
237
238        let permutation: Permutation = Construct::new();
239        let ins: Vec<BigUint> = vec![
240            1usize.into(),
241            2usize.into(),
242            3usize.into(),
243            4usize.into(),
244        ];
245        let outs: Vec<BigUint> = vec![
246            1usize.into(),
247            2usize.into(),
248            6usize.into(),
249            24usize.into(),
250        ];
251        for i in 0..ins.len() {
252            assert_eq!(permutation.count(&ins[i]), outs[i]);
253        }
254
255        let mut pos: Vec<BigUint> = Vec::new();
256        let ref dim: BigUint = 4usize.into();
257        let count: usize = permutation.count(dim).try_into().unwrap();
258        for i in 0usize..count {
259            permutation.to_pos(dim, i.into(), &mut pos);
260            let index = permutation.to_index(dim, &pos);
261            assert_eq!(index, i.into());
262        }
263    }
264
265    #[test]
266    fn of() {
267        let space: Permutation<Of<Pair>> = Construct::new();
268        let ref dim = 3;
269        let count = space.count(dim);
270        let mut pos = space.zero(dim);
271        for i in 0..count {
272            space.to_pos(dim, i, &mut pos);
273            let index = space.to_index(dim, &pos);
274            assert_eq!(index, i);
275        }
276    }
277
278    #[test]
279    fn of_big() {
280        use std::convert::TryInto;
281
282        let space: Permutation<Of<Pair>> = Construct::new();
283        let ref dim: BigUint = 3usize.into();
284        let count: usize = space.count(dim).try_into().unwrap();
285        let mut pos = space.zero(dim);
286        for i in 0..count {
287            space.to_pos(dim, i.into(), &mut pos);
288            let index = space.to_index(dim, &pos);
289            assert_eq!(index, i.into());
290        }
291    }
292}
discrete/permutation.rs

discrete/
permutation.rs
