qsym2/permutation/
mod.rs

1//! Permutations as elements in symmetric groups.
2
3use std::collections::{HashMap, HashSet, VecDeque};
4use std::fmt;
5use std::hash::Hash;
6use std::ops::Mul;
7
8use anyhow::{self, format_err};
9use bitvec::prelude::*;
10use derive_builder::Builder;
11use factorial::Factorial;
12use indexmap::IndexSet;
13use num::{integer::lcm, Integer, Unsigned};
14use num_traits::{Inv, Pow, PrimInt};
15use serde::{Deserialize, Serialize};
16
17use crate::group::FiniteOrder;
18
19mod permutation_group;
20mod permutation_symbols;
21
22#[cfg(test)]
23mod permutation_tests;
24
25// =================
26// Trait definitions
27// =================
28
29/// Trait defining a permutable collection consisting of discrete and distinguishable items that
30/// can be permuted.
31pub trait PermutableCollection
32where
33    Self: Sized,
34    Self::Rank: PermutationRank,
35{
36    /// The type of the rank of the permutation.
37    type Rank;
38
39    /// Determines the permutation, if any, that maps `self` to `other`.
40    fn get_perm_of(&self, other: &Self) -> Option<Permutation<Self::Rank>>;
41
42    /// Permutes the items in the current collection by `perm` and returns a new collection with
43    /// the permuted items.
44    fn permute(&self, perm: &Permutation<Self::Rank>) -> Result<Self, anyhow::Error>;
45
46    /// Permutes in-place the items in the current collection by `perm`.
47    fn permute_mut(&mut self, perm: &Permutation<Self::Rank>) -> Result<(), anyhow::Error>;
48}
49
50/// Trait defining an action on a permutable collection that can be converted into an equivalent
51/// permutation acting on that collection.
52pub trait IntoPermutation<C: PermutableCollection> {
53    /// Determines the permutation of `rhs` considered as a collection induced by the action of
54    /// `self` on `rhs` considered as an element in its domain. If no such permutation could be
55    /// found, `None` is returned.
56    fn act_permute(&self, rhs: &C) -> Option<Permutation<C::Rank>>;
57}
58
59/// Trait for generic permutation rank types.
60pub trait PermutationRank:
61    Integer + Unsigned + BitStore + PrimInt + Hash + TryFrom<usize> + Into<usize> + Serialize
62{
63}
64
65/// Blanket implementation of `PermutationRank`.
66impl<T> PermutationRank for T
67where
68    T: Integer + Unsigned + BitStore + PrimInt + Hash + TryFrom<usize> + Into<usize> + Serialize,
69    <T as TryFrom<usize>>::Error: fmt::Debug,
70    std::ops::Range<T>: Iterator + DoubleEndedIterator,
71    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
72    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
73    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
74{
75}
76
77// ==================
78// Struct definitions
79// ==================
80
81/// Structure to manage permutation actions of a finite set.
82#[derive(Builder, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
83pub struct Permutation<T: PermutationRank> {
84    /// If the permutation is to act on an ordered sequence of $`n`$ integers, $`0, 1, \ldots, n`$,
85    /// then this gives the result of the action.
86    #[builder(setter(custom))]
87    image: Vec<T>,
88}
89
90impl<T: PermutationRank> PermutationBuilder<T> {
91    /// If the permutation is to act on an ordered sequence of $`n`$ integers, $`0, 1, \ldots, n`$,
92    /// then this gives the result of the action.
93    pub fn image(&mut self, perm: Vec<T>) -> &mut Self {
94        let mut uniq = HashSet::<T>::new();
95        // assert!(
96        //     perm.iter().all(move |x| uniq.insert(*x)),
97        //     "The permutation image `{perm:?}` contains repeated elements."
98        // );
99        if perm.iter().all(move |x| uniq.insert(*x)) {
100            // The permutation contains all distinct elements.
101            self.image = Some(perm);
102        }
103        self
104    }
105}
106
107impl<T: PermutationRank> Permutation<T> {
108    /// Returns a builder to construct a new permutation.
109    #[must_use]
110    fn builder() -> PermutationBuilder<T> {
111        PermutationBuilder::default()
112    }
113
114    /// Constructs a permutation from the image of its action on an ordered sequence of integers,
115    /// $`0, 1, \ldots`$.
116    ///
117    /// # Arguments
118    ///
119    /// * `image` - The image of the permutation when acting on an ordered sequence of integers,
120    /// $`0, 1, \ldots`$.
121    ///
122    /// # Returns
123    ///
124    /// The corresponding permutation.
125    ///
126    /// # Panics
127    ///
128    /// Panics if `image` contains repeated elements.
129    pub fn from_image(image: Vec<T>) -> Result<Self, anyhow::Error> {
130        Self::builder()
131            .image(image.clone())
132            .build()
133            .map_err(|err| format_err!(err))
134    }
135
136    /// Constructs a permutation from its disjoint cycles.
137    ///
138    /// # Arguments
139    ///
140    /// * `cycles` - The disjoint cycles defining the permutation.
141    ///
142    /// # Returns
143    ///
144    /// The corresponding permutation.
145    ///
146    /// # Panics
147    ///
148    /// Panics if the cycles in `cycles` contain repeated elements.
149    pub fn from_cycles(cycles: &[Vec<T>]) -> Result<Self, anyhow::Error> {
150        let mut uniq = HashSet::<T>::new();
151        assert!(
152            cycles.iter().flatten().all(move |x| uniq.insert(*x)),
153            "The permutation cycles `{cycles:?}` contains repeated elements."
154        );
155        let mut image_map = cycles
156            .iter()
157            .flat_map(|cycle| {
158                let start = *cycle.first().expect("Empty cycles are not permitted.");
159                let end = *cycle.last().expect("Empty cycles are not permitted.");
160                cycle
161                    .windows(2)
162                    .map(|pair| {
163                        let idx = pair[0];
164                        let img = pair[1];
165                        (idx, img)
166                    })
167                    .chain([(end, start)])
168            })
169            .collect::<Vec<(T, T)>>();
170        image_map.sort();
171        let image = image_map
172            .into_iter()
173            .map(|(_, img)| img)
174            .collect::<Vec<T>>();
175        Self::from_image(image)
176    }
177
178    /// Constructs a permutation from its Lehmer encoding.
179    ///
180    /// See [here](https://en.wikipedia.org/wiki/Lehmer_code) for additional information.
181    pub fn from_lehmer(lehmer: Vec<T>) -> Result<Self, anyhow::Error>
182    where
183        <T as TryFrom<usize>>::Error: fmt::Debug,
184        std::ops::Range<T>: Iterator,
185        VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
186    {
187        let n = T::try_from(lehmer.len()).expect("Unable to convert the `lehmer` length to `u8`.");
188        let mut remaining = (T::zero()..n).collect::<VecDeque<T>>();
189        let image = lehmer
190            .iter()
191            .map(|&k| {
192                remaining.remove(k.into()).unwrap_or_else(|| {
193                    panic!("Unable to retrieve element index `{k:?}` from `{remaining:?}`.")
194                })
195            })
196            .collect::<Vec<_>>();
197        Self::from_image(image)
198    }
199
200    /// Constructs a permutation from the integer index obtained from a Lehmer encoding.
201    ///
202    /// See [here](https://en.wikipedia.org/wiki/Lehmer_code) and
203    /// Korf, R. E. Linear-time disk-based implicit graph search. *J. ACM* **55**, 1–40 (2008).
204    /// for additional information.
205    ///
206    /// # Arguments
207    ///
208    /// * `index` - An integer index.
209    /// * `rank` - A rank for the permutation to be constructed.
210    ///
211    /// # Returns
212    ///
213    /// Returns the corresponding permutation.
214    ///
215    /// # Errors
216    ///
217    /// If `index` is not valid for a permutation of rank `rank`.
218    pub fn from_lehmer_index(index: usize, rank: T) -> Result<Self, anyhow::Error>
219    where
220        <T as TryFrom<usize>>::Error: fmt::Debug,
221        std::ops::Range<T>: Iterator,
222        VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
223    {
224        let mut quotient = index;
225        let mut lehmer: VecDeque<T> = VecDeque::new();
226        let mut i = 1usize;
227        while quotient != 0 {
228            if i == 1 {
229                lehmer.push_front(T::zero());
230            } else {
231                lehmer.push_front(T::try_from(quotient.rem_euclid(i)).unwrap());
232                quotient = quotient.div_euclid(i);
233            }
234            i += 1;
235        }
236        if lehmer.len() > rank.into() {
237            Err(format_err!(
238                "The Lehmer encode length is larger than the rank of the permutation."
239            ))
240        } else {
241            while lehmer.len() < rank.into() {
242                lehmer.push_front(T::zero());
243            }
244            Self::from_lehmer(lehmer.into_iter().collect::<Vec<_>>())
245        }
246    }
247
248    /// The rank of the permutation.
249    pub fn rank(&self) -> T {
250        T::try_from(self.image.len()).unwrap_or_else(|_| {
251            panic!(
252                "The rank of `{:?}` is too large to be represented as `u8`.",
253                self.image
254            )
255        })
256    }
257
258    /// If the permutation is to act on an ordered sequence of integers, $`0, 1, \ldots`$, then
259    /// this gives the result of the action.
260    pub fn image(&self) -> &Vec<T> {
261        &self.image
262    }
263
264    /// Obtains the cycle representation of the permutation.
265    pub fn cycles(&self) -> Vec<Vec<T>>
266    where
267        std::ops::Range<T>: Iterator + DoubleEndedIterator,
268        Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
269        IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
270    {
271        let image = &self.image;
272        let rank = self.rank();
273        let mut remaining_indices = (T::zero()..rank).rev().collect::<IndexSet<T>>();
274        let mut cycles: Vec<Vec<T>> = Vec::with_capacity(rank.into());
275        while !remaining_indices.is_empty() {
276            let start = remaining_indices
277                .pop()
278                .expect("`remaining_indices` should not be empty.");
279            let mut cycle: Vec<T> = Vec::with_capacity(remaining_indices.len());
280            cycle.push(start);
281            let mut idx = start;
282            while image[idx.into()] != start {
283                idx = image[idx.into()];
284                assert!(remaining_indices.shift_remove(&idx));
285                cycle.push(idx);
286            }
287            cycle.shrink_to_fit();
288            cycles.push(cycle);
289        }
290        cycles.shrink_to_fit();
291        cycles.sort_by_key(|cycle| (!cycle.len(), cycle.clone()));
292        cycles
293    }
294
295    /// Returns the pattern of the cycle representation of the permutation.
296    pub fn cycle_pattern(&self) -> Vec<T>
297    where
298        <T as TryFrom<usize>>::Error: fmt::Debug,
299        std::ops::Range<T>: Iterator + DoubleEndedIterator,
300        Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
301        IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
302    {
303        self.cycles()
304            .iter()
305            .map(|cycle| {
306                T::try_from(cycle.len()).expect("Some cycle lengths are too long for `u8`.")
307            })
308            .collect::<Vec<T>>()
309    }
310
311    /// Returns `true` if this permutation is the identity permutation for this rank.
312    pub fn is_identity(&self) -> bool
313    where
314        <T as TryFrom<usize>>::Error: fmt::Debug,
315    {
316        self.lehmer_index(None) == 0
317    }
318
319    /// Returns the Lehmer encoding of the permutation.
320    ///
321    /// # Arguments
322    ///
323    /// * `count_ones_opt` - An optional hashmap containing the number of ones in each of the
324    /// possible bit vectors of length [`Self::rank`].
325    ///
326    /// # Returns
327    ///
328    /// The Lehmer encoding of this permutation. See
329    /// [here](https://en.wikipedia.org/wiki/Lehmer_code) for additional information.
330    pub fn lehmer(&self, count_ones_opt: Option<&HashMap<BitVec<T, Lsb0>, T>>) -> Vec<T>
331    where
332        <T as TryFrom<usize>>::Error: fmt::Debug,
333    {
334        let mut bv: BitVec<T, Lsb0> = bitvec![T, Lsb0; 0; self.rank().into()];
335        let n = self.rank();
336        self.image
337            .iter()
338            .enumerate()
339            .map(|(i, &k)| {
340                let flipped_bv_k = !bv[k.into()];
341                bv.set(k.into(), flipped_bv_k);
342                if i == 0 {
343                    k
344                } else if i == (n - T::one()).into() {
345                    T::zero()
346                } else {
347                    let mut bv_k = bv.clone();
348                    bv_k.shift_right((n - k).into());
349                    k - if let Some(count_ones) = count_ones_opt {
350                        *(count_ones.get(&bv_k).unwrap_or_else(|| {
351                            panic!("Unable to count the number of ones in `{bv}`.")
352                        }))
353                    } else {
354                        T::try_from(bv_k.count_ones())
355                            .expect("Unable to convert the number of ones to `u8`.")
356                    }
357                }
358            })
359            .collect::<Vec<T>>()
360    }
361
362    /// Returns the integer corresponding to the Lehmer encoding of this permutation.
363    ///
364    /// See [here](https://en.wikipedia.org/wiki/Lehmer_code) and
365    /// Korf, R. E. Linear-time disk-based implicit graph search. *J. ACM* **55**, 1–40 (2008).
366    /// for additional information.
367    ///
368    /// # Arguments
369    ///
370    /// * `count_ones_opt` - An optional hashmap containing the number of ones in each of the
371    /// possible bit vectors of length [`Self::rank`].
372    ///
373    /// # Returns
374    ///
375    /// Returns the integer corresponding to the Lehmer encoding of this permutation.
376    pub fn lehmer_index(&self, count_ones_opt: Option<&HashMap<BitVec<T, Lsb0>, T>>) -> usize
377    where
378        <T as TryFrom<usize>>::Error: fmt::Debug,
379    {
380        let lehmer = self.lehmer(count_ones_opt);
381        let n = self.rank().into() - 1;
382        if n == 0 {
383            0
384        } else {
385            lehmer
386                .into_iter()
387                .enumerate()
388                .map(|(i, l)| {
389                    l.into()
390                        * (n - i).checked_factorial().unwrap_or_else(|| {
391                            panic!("The factorial of `{}` cannot be correctly computed.", n - i)
392                        })
393                })
394                .sum()
395        }
396    }
397}
398
399// =====================
400// Trait implementations
401// =====================
402
403// -------
404// Display
405// -------
406impl<T: PermutationRank + fmt::Display> fmt::Display for Permutation<T> {
407    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
408        write!(
409            f,
410            "π({})",
411            self.image
412                .iter()
413                .map(|i| i.to_string())
414                .collect::<Vec<_>>()
415                .join(".")
416        )
417    }
418}
419
420// ---
421// Mul
422// ---
423impl<T: PermutationRank> Mul<&'_ Permutation<T>> for &Permutation<T>
424where
425    std::ops::Range<T>: Iterator + DoubleEndedIterator,
426    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
427    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
428    <T as TryFrom<usize>>::Error: fmt::Debug,
429    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
430{
431    type Output = Permutation<T>;
432
433    fn mul(self, rhs: &Permutation<T>) -> Self::Output {
434        assert_eq!(
435            self.rank(),
436            rhs.rank(),
437            "The ranks of two multiplying permutations do not match."
438        );
439        Self::Output::builder()
440            .image(
441                rhs.image
442                    .iter()
443                    .map(|&ri| self.image[ri.into()])
444                    .collect::<Vec<T>>(),
445            )
446            .build()
447            .expect("Unable to construct a product `Permutation`.")
448    }
449}
450
451impl<T: PermutationRank> Mul<&'_ Permutation<T>> for Permutation<T>
452where
453    std::ops::Range<T>: Iterator + DoubleEndedIterator,
454    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
455    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
456    <T as TryFrom<usize>>::Error: fmt::Debug,
457    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
458{
459    type Output = Permutation<T>;
460
461    fn mul(self, rhs: &Permutation<T>) -> Self::Output {
462        &self * rhs
463    }
464}
465
466impl<T: PermutationRank> Mul<Permutation<T>> for Permutation<T>
467where
468    std::ops::Range<T>: Iterator + DoubleEndedIterator,
469    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
470    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
471    <T as TryFrom<usize>>::Error: fmt::Debug,
472    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
473{
474    type Output = Permutation<T>;
475
476    fn mul(self, rhs: Permutation<T>) -> Self::Output {
477        &self * &rhs
478    }
479}
480
481impl<T: PermutationRank> Mul<Permutation<T>> for &Permutation<T>
482where
483    std::ops::Range<T>: Iterator + DoubleEndedIterator,
484    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
485    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
486    <T as TryFrom<usize>>::Error: fmt::Debug,
487    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
488{
489    type Output = Permutation<T>;
490
491    fn mul(self, rhs: Permutation<T>) -> Self::Output {
492        self * &rhs
493    }
494}
495
496// ---
497// Inv
498// ---
499impl<T: PermutationRank> Inv for &Permutation<T>
500where
501    std::ops::Range<T>: Iterator + DoubleEndedIterator,
502    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
503    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
504    <T as TryFrom<usize>>::Error: fmt::Debug,
505    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
506{
507    type Output = Permutation<T>;
508
509    fn inv(self) -> Self::Output {
510        let mut image_inv = (T::zero()..self.rank()).collect::<Vec<T>>();
511        image_inv.sort_by_key(|&i| self.image[i.into()]);
512        Self::Output::builder()
513            .image(image_inv)
514            .build()
515            .expect("Unable to construct an inverse `Permutation`.")
516    }
517}
518
519impl<T: PermutationRank> Inv for Permutation<T>
520where
521    std::ops::Range<T>: Iterator + DoubleEndedIterator,
522    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
523    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
524    <T as TryFrom<usize>>::Error: fmt::Debug,
525    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
526{
527    type Output = Permutation<T>;
528
529    fn inv(self) -> Self::Output {
530        (&self).inv()
531    }
532}
533
534// ---
535// Pow
536// ---
537impl<T: PermutationRank> Pow<i32> for &Permutation<T>
538where
539    std::ops::Range<T>: Iterator + DoubleEndedIterator,
540    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
541    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
542    <T as TryFrom<usize>>::Error: fmt::Debug,
543    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
544{
545    type Output = Permutation<T>;
546
547    fn pow(self, rhs: i32) -> Self::Output {
548        if rhs == 0 {
549            Self::Output::builder()
550                .image((T::zero()..self.rank()).collect::<Vec<T>>())
551                .build()
552                .expect("Unable to construct an identity `Permutation`.")
553        } else if rhs > 0 {
554            self * self.pow(rhs - 1)
555        } else {
556            let rhs_p = -rhs;
557            (self * self.pow(rhs_p - 1)).inv()
558        }
559    }
560}
561
562impl<T: PermutationRank> Pow<i32> for Permutation<T>
563where
564    std::ops::Range<T>: Iterator + DoubleEndedIterator,
565    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
566    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
567    <T as TryFrom<usize>>::Error: fmt::Debug,
568    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
569{
570    type Output = Permutation<T>;
571
572    fn pow(self, rhs: i32) -> Self::Output {
573        (&self).pow(rhs)
574    }
575}
576
577// -----------
578// FiniteOrder
579// -----------
580impl<T: PermutationRank + fmt::Display> FiniteOrder for Permutation<T>
581where
582    u32: From<T>,
583    std::ops::Range<T>: Iterator + DoubleEndedIterator,
584    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
585    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
586    <T as TryFrom<usize>>::Error: fmt::Debug,
587    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
588{
589    type Int = u32;
590
591    /// Calculates the order of this permutation. This is the lowest common multiplier of the
592    /// lengths of the disjoint cycles constituting this permutation.
593    fn order(&self) -> Self::Int {
594        u32::try_from(
595            self.cycle_pattern()
596                .iter()
597                .cloned()
598                .reduce(lcm)
599                .unwrap_or_else(|| {
600                    panic!("Unable to determine the permutation order of `{self}`.")
601                }),
602        )
603        .expect("Unable to convert the permutation order to `u32`.")
604    }
605}
606
607// =========
608// Functions
609// =========
610/// Permutes the items in a vector in-place.
611///
612/// # Arguments
613///
614/// * `vec` - An exclusive reference to a vector of items to be permuted.
615/// * `perm` - A shared reference to a permutation determining how the items are to be permuted.
616pub(crate) fn permute_inplace<T>(vec: &mut Vec<T>, perm: &Permutation<usize>) {
617    assert_eq!(
618        perm.rank(),
619        vec.len(),
620        "The permutation rank does not match the number of items in the vector."
621    );
622    let mut image = perm.image().clone();
623    for idx in 0..vec.len() {
624        if image[idx] != idx {
625            let mut current_idx = idx;
626            loop {
627                let target_idx = image[current_idx];
628                image[current_idx] = current_idx;
629                if image[target_idx] == target_idx {
630                    break;
631                }
632                vec.swap(current_idx, target_idx);
633                current_idx = target_idx;
634            }
635        }
636    }
637}
qsym2/permutation/mod.rs

qsym2/permutation/
mod.rs
