rusty_perm/
perm_type.rs

1use crate::{common::*, perm_trait::Permutation, size::PermSize};
2
3#[cfg(feature = "std")]
4pub use with_std::*;
5pub use without_std::*;
6
7/// Generic permutation data structure.
8#[derive(Clone, Debug, Eq, Hash)]
9pub struct Perm<S>
10where
11    S: PermSize,
12{
13    pub(super) indices: S::Container,
14}
15
16impl<SL, SR> PartialEq<Perm<SR>> for Perm<SL>
17where
18    SL: PermSize,
19    SR: PermSize,
20{
21    fn eq(&self, other: &Perm<SR>) -> bool {
22        self.indices.as_ref() == other.indices.as_ref()
23    }
24}
25
26mod without_std {
27    use super::*;
28    use crate::size::Static;
29
30    /// Permutation type with static size known in compile time.
31    pub type PermS<const SIZE: usize> = Perm<Static<{ SIZE }>>;
32
33    /// Permutation type with static size 0.
34    pub type Perm0 = PermS<0>;
35
36    /// Permutation type with static size 1.
37    pub type Perm1 = PermS<1>;
38
39    /// Permutation type with static size 2.
40    pub type Perm2 = PermS<2>;
41
42    /// Permutation type with static size 4.
43    pub type Perm4 = PermS<4>;
44
45    /// Permutation type with static size 5.
46    pub type Perm5 = PermS<5>;
47
48    /// Permutation type with static size 6.
49    pub type Perm6 = PermS<6>;
50
51    /// Permutation type with static size 7.
52    pub type Perm7 = PermS<7>;
53
54    /// Permutation type with static size 8.
55    pub type Perm8 = PermS<8>;
56
57    /// Permutation type with static size 9.
58    pub type Perm9 = PermS<9>;
59
60    /// Permutation type with static size 10.
61    pub type Perm10 = PermS<10>;
62
63    /// Permutation type with static size 11.
64    pub type Perm11 = PermS<11>;
65
66    /// Permutation type with static size 12.
67    pub type Perm12 = PermS<12>;
68
69    /// Permutation type with static size 13.
70    pub type Perm13 = PermS<13>;
71
72    /// Permutation type with static size 14.
73    pub type Perm14 = PermS<14>;
74
75    /// Permutation type with static size 15.
76    pub type Perm15 = PermS<15>;
77
78    /// Permutation type with static size 16.
79    pub type Perm16 = PermS<16>;
80
81    /// Permutation type with static size 17.
82    pub type Perm17 = PermS<17>;
83
84    /// Permutation type with static size 18.
85    pub type Perm18 = PermS<18>;
86
87    /// Permutation type with static size 19.
88    pub type Perm19 = PermS<19>;
89
90    /// Permutation type with static size 20.
91    pub type Perm20 = PermS<20>;
92
93    /// Permutation type with static size 21.
94    pub type Perm21 = PermS<21>;
95
96    /// Permutation type with static size 22.
97    pub type Perm22 = PermS<22>;
98
99    /// Permutation type with static size 23.
100    pub type Perm23 = PermS<23>;
101
102    /// Permutation type with static size 24.
103    pub type Perm24 = PermS<24>;
104
105    /// Permutation type with static size 25.
106    pub type Perm25 = PermS<25>;
107
108    /// Permutation type with static size 26.
109    pub type Perm26 = PermS<26>;
110
111    /// Permutation type with static size 27.
112    pub type Perm27 = PermS<27>;
113
114    /// Permutation type with static size 28.
115    pub type Perm28 = PermS<28>;
116
117    /// Permutation type with static size 29.
118    pub type Perm29 = PermS<29>;
119
120    /// Permutation type with static size 30.
121    pub type Perm30 = PermS<30>;
122
123    /// Permutation type with static size 31.
124    pub type Perm31 = PermS<31>;
125
126    /// Permutation type with static size 32.
127    pub type Perm32 = PermS<32>;
128
129    impl<const SIZE: usize> PermS<SIZE> {
130        pub fn identity() -> Self {
131            let mut indices = [0; SIZE];
132            (0..SIZE).for_each(|index| indices[index] = index);
133            Self { indices }
134        }
135
136        pub fn swap(first: usize, second: usize) -> Option<Self> {
137            if first >= SIZE || second >= SIZE || first == second {
138                return None;
139            }
140
141            let min = first.min(second);
142            let max = first.max(second);
143
144            let mut indices = [0; SIZE];
145
146            indices[min] = max;
147            indices[max] = min;
148            (0..min).for_each(|index| {
149                indices[index] = index;
150            });
151            ((min + 1)..max).for_each(|index| {
152                indices[index] = index;
153            });
154            ((max + 1)..SIZE).for_each(|index| {
155                indices[index] = index;
156            });
157
158            Some(Self { indices })
159        }
160
161        pub fn cycle() -> Self {
162            let mut indices = [0; SIZE];
163            iter::once(SIZE - 1)
164                .chain(0..(SIZE - 1))
165                .enumerate()
166                .for_each(|(dst, src)| {
167                    indices[dst] = src;
168                });
169            Self { indices }
170        }
171
172        pub fn reverse_cycle() -> Self {
173            let mut indices = [0; SIZE];
174            (1..SIZE)
175                .chain(iter::once(0))
176                .enumerate()
177                .for_each(|(dst, src)| {
178                    indices[dst] = src;
179                });
180            Self { indices }
181        }
182
183        pub fn permute_indices(&self, perm: &PermS<SIZE>) -> Self {
184            self.conjugate_with(perm)
185        }
186
187        pub fn conjugate_with(&self, other: &PermS<SIZE>) -> Self {
188            &(&other.inverse() * self) * other
189        }
190
191        pub fn to_size<const NEW_SIZE: usize>(&self) -> Option<PermS<NEW_SIZE>> {
192            if SIZE > NEW_SIZE {
193                for dst in NEW_SIZE..SIZE {
194                    let src = self.indices[dst];
195                    if src != dst {
196                        return None;
197                    }
198                }
199
200                let mut new_indices = [0; NEW_SIZE];
201                new_indices.copy_from_slice(&self.indices[..NEW_SIZE]);
202                Some(PermS {
203                    indices: new_indices,
204                })
205            } else {
206                let mut new_indices = [0; NEW_SIZE];
207                new_indices[..SIZE].copy_from_slice(&self.indices[..SIZE]);
208
209                (SIZE..NEW_SIZE).for_each(|index| {
210                    new_indices[index] = index;
211                });
212
213                Some(PermS {
214                    indices: new_indices,
215                })
216            }
217        }
218    }
219
220    impl Perm0 {
221        pub fn empty() -> Self {
222            Self { indices: [] }
223        }
224    }
225
226    impl Perm1 {
227        pub fn unit() -> Self {
228            Self { indices: [0] }
229        }
230    }
231
232    impl Perm2 {
233        pub fn swap2() -> Self {
234            Self { indices: [1, 0] }
235        }
236    }
237
238    #[cfg(test)]
239    mod tests {
240        use super::*;
241        use crate::{apply::PermApply, from_indices::PermFromIndices};
242        use rand::prelude::*;
243
244        #[test]
245        fn static_identity() {
246            const SIZE: usize = 2014;
247
248            let perm = PermS::<SIZE>::identity();
249
250            let mut rng = rand::thread_rng();
251            let mut orig = [0usize; SIZE];
252            rng.fill(orig.as_mut());
253
254            let mut new = orig.clone();
255            perm.apply(&mut new);
256
257            assert_eq!(orig, new);
258        }
259
260        #[test]
261        fn static_swap() {
262            let perm = PermS::<6>::swap(5, 3).unwrap();
263            assert_eq!(perm.indices(), &[0, 1, 2, 5, 4, 3]);
264        }
265
266        #[test]
267        fn static_permute_indices() {
268            let index_map = PermS::from_indices([3, 5, 0, 1, 2, 4]).unwrap();
269            let orig = PermS::<6>::swap(5, 3).unwrap();
270            let new = orig.permute_indices(&index_map);
271            assert_eq!(new, PermS::<6>::swap(0, 1).unwrap());
272        }
273    }
274}
275
276#[cfg(feature = "std")]
277mod with_std {
278    use super::*;
279    use crate::{product::PermProduct, size::Dynamic};
280
281    /// Permutation type with runtime size.
282    pub type PermD = Perm<Dynamic>;
283
284    impl PermD {
285        pub fn empty() -> Self {
286            Self { indices: vec![] }
287        }
288
289        pub fn unit() -> Self {
290            Self { indices: vec![0] }
291        }
292
293        pub fn swap(size: usize, first: usize, second: usize) -> Option<Self> {
294            if first >= size || second >= size || first == second {
295                return None;
296            }
297
298            let min = first.min(second);
299            let max = first.max(second);
300
301            let indices: Vec<_> = (0..min)
302                .chain(iter::once(max))
303                .chain((min + 1)..max)
304                .chain(iter::once(min))
305                .chain((max + 1)..size)
306                .collect();
307
308            Some(Self { indices })
309        }
310
311        pub fn identity(size: usize) -> Self {
312            let mut indices = vec![0; size];
313            (0..size).for_each(|index| indices[index] = index);
314            Self { indices }
315        }
316
317        pub fn cycle(size: usize) -> Self {
318            let mut indices = vec![0; size];
319            iter::once(size - 1)
320                .chain(0..(size - 1))
321                .enumerate()
322                .for_each(|(dst, src)| {
323                    indices[dst] = src;
324                });
325            Self { indices }
326        }
327
328        pub fn reverse_cycle(size: usize) -> Self {
329            let mut indices = vec![0; size];
330            (1..size)
331                .chain(iter::once(0))
332                .enumerate()
333                .for_each(|(dst, src)| {
334                    indices[dst] = src;
335                });
336            Self { indices }
337        }
338
339        pub fn permute_indices(&self, perm: &PermD) -> Option<Self> {
340            self.conjugate_with(perm)
341        }
342
343        pub fn conjugate_with(&self, other: &PermD) -> Option<Self> {
344            other.inverse().perm_product(self)?.perm_product(other)
345        }
346
347        pub fn to_size(&self, new_size: usize) -> Option<PermD> {
348            let orig_size = self.indices.len();
349            if orig_size > new_size {
350                for dst in new_size..orig_size {
351                    let src = self.indices[dst];
352                    if src != dst {
353                        return None;
354                    }
355                }
356
357                let mut new_indices = vec![0; new_size];
358                new_indices.copy_from_slice(&self.indices[..new_size]);
359                Some(PermD {
360                    indices: new_indices,
361                })
362            } else {
363                let mut new_indices = vec![0; new_size];
364                new_indices[..orig_size].copy_from_slice(&self.indices[..orig_size]);
365
366                (orig_size..new_size).for_each(|index| {
367                    new_indices[index] = index;
368                });
369
370                Some(PermD {
371                    indices: new_indices,
372                })
373            }
374        }
375
376        pub fn into_static<const SIZE: usize>(self) -> Option<PermS<SIZE>> {
377            let Self { indices } = self;
378            let indices = <[usize; SIZE]>::try_from(indices).ok()?;
379            Some(PermS { indices })
380        }
381    }
382
383    impl<const SIZE: usize> PermS<SIZE> {
384        pub fn into_dynamic(self) -> PermD {
385            let Self { indices } = self;
386            PermD {
387                indices: Vec::from(indices),
388            }
389        }
390    }
391
392    #[cfg(test)]
393    mod tests {
394        use super::*;
395        use crate::{apply::PermApply, from_indices::PermFromIndices};
396        use rand::prelude::*;
397
398        #[test]
399        fn dynamic_identity() {
400            const SIZE: usize = 2014;
401
402            let perm = PermD::identity(SIZE);
403
404            let mut rng = rand::thread_rng();
405            let mut orig = [0usize; SIZE];
406            rng.fill(orig.as_mut());
407
408            let mut new = orig.clone();
409            perm.apply(&mut new).unwrap();
410
411            assert_eq!(orig, new);
412        }
413
414        #[test]
415        fn dynamic_swap() {
416            let perm = PermD::swap(6, 5, 3).unwrap();
417            assert_eq!(perm.indices(), &[0, 1, 2, 5, 4, 3]);
418        }
419
420        #[test]
421        fn dynamic_permute_indices() {
422            let index_map = PermD::from_indices([3, 5, 0, 1, 2, 4]).unwrap();
423            let orig = PermD::swap(6, 5, 3).unwrap();
424            let new = orig.permute_indices(&index_map).unwrap();
425            assert_eq!(new, PermD::swap(6, 0, 1).unwrap());
426        }
427    }
428}
rusty_perm/perm_type.rs

rusty_perm/
perm_type.rs
