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!("The Lehmer encode length is larger than the rank of the permutation."))
238        } else {
239            while lehmer.len() < rank.into() {
240                lehmer.push_front(T::zero());
241            }
242            Self::from_lehmer(lehmer.into_iter().collect::<Vec<_>>())
243        }
244    }
245
246    /// The rank of the permutation.
247    pub fn rank(&self) -> T {
248        T::try_from(self.image.len()).unwrap_or_else(|_| {
249            panic!(
250                "The rank of `{:?}` is too large to be represented as `u8`.",
251                self.image
252            )
253        })
254    }
255
256    /// If the permutation is to act on an ordered sequence of integers, $`0, 1, \ldots`$, then
257    /// this gives the result of the action.
258    pub fn image(&self) -> &Vec<T> {
259        &self.image
260    }
261
262    /// Obtains the cycle representation of the permutation.
263    pub fn cycles(&self) -> Vec<Vec<T>>
264    where
265        std::ops::Range<T>: Iterator + DoubleEndedIterator,
266        Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
267        IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
268    {
269        let image = &self.image;
270        let rank = self.rank();
271        let mut remaining_indices = (T::zero()..rank).rev().collect::<IndexSet<T>>();
272        let mut cycles: Vec<Vec<T>> = Vec::with_capacity(rank.into());
273        while !remaining_indices.is_empty() {
274            let start = remaining_indices
275                .pop()
276                .expect("`remaining_indices` should not be empty.");
277            let mut cycle: Vec<T> = Vec::with_capacity(remaining_indices.len());
278            cycle.push(start);
279            let mut idx = start;
280            while image[idx.into()] != start {
281                idx = image[idx.into()];
282                assert!(remaining_indices.shift_remove(&idx));
283                cycle.push(idx);
284            }
285            cycle.shrink_to_fit();
286            cycles.push(cycle);
287        }
288        cycles.shrink_to_fit();
289        cycles.sort_by_key(|cycle| (!cycle.len(), cycle.clone()));
290        cycles
291    }
292
293    /// Returns the pattern of the cycle representation of the permutation.
294    pub fn cycle_pattern(&self) -> Vec<T>
295    where
296        <T as TryFrom<usize>>::Error: fmt::Debug,
297        std::ops::Range<T>: Iterator + DoubleEndedIterator,
298        Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
299        IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
300    {
301        self.cycles()
302            .iter()
303            .map(|cycle| {
304                T::try_from(cycle.len()).expect("Some cycle lengths are too long for `u8`.")
305            })
306            .collect::<Vec<T>>()
307    }
308
309    /// Returns `true` if this permutation is the identity permutation for this rank.
310    pub fn is_identity(&self) -> bool
311    where
312        <T as TryFrom<usize>>::Error: fmt::Debug,
313    {
314        self.lehmer_index(None) == 0
315    }
316
317    /// Returns the Lehmer encoding of the permutation.
318    ///
319    /// # Arguments
320    ///
321    /// * `count_ones_opt` - An optional hashmap containing the number of ones in each of the
322    /// possible bit vectors of length [`Self::rank`].
323    ///
324    /// # Returns
325    ///
326    /// The Lehmer encoding of this permutation. See
327    /// [here](https://en.wikipedia.org/wiki/Lehmer_code) for additional information.
328    pub fn lehmer(&self, count_ones_opt: Option<&HashMap<BitVec<T, Lsb0>, T>>) -> Vec<T>
329    where
330        <T as TryFrom<usize>>::Error: fmt::Debug,
331    {
332        let mut bv: BitVec<T, Lsb0> = bitvec![T, Lsb0; 0; self.rank().into()];
333        let n = self.rank();
334        self.image
335            .iter()
336            .enumerate()
337            .map(|(i, &k)| {
338                let flipped_bv_k = !bv[k.into()];
339                bv.set(k.into(), flipped_bv_k);
340                if i == 0 {
341                    k
342                } else if i == (n - T::one()).into() {
343                    T::zero()
344                } else {
345                    let mut bv_k = bv.clone();
346                    bv_k.shift_right((n - k).into());
347                    k - if let Some(count_ones) = count_ones_opt {
348                        *(count_ones.get(&bv_k).unwrap_or_else(|| {
349                            panic!("Unable to count the number of ones in `{bv}`.")
350                        }))
351                    } else {
352                        T::try_from(bv_k.count_ones())
353                            .expect("Unable to convert the number of ones to `u8`.")
354                    }
355                }
356            })
357            .collect::<Vec<T>>()
358    }
359
360    /// Returns the integer corresponding to the Lehmer encoding of this permutation.
361    ///
362    /// See [here](https://en.wikipedia.org/wiki/Lehmer_code) and
363    /// Korf, R. E. Linear-time disk-based implicit graph search. *J. ACM* **55**, 1–40 (2008).
364    /// for additional information.
365    ///
366    /// # Arguments
367    ///
368    /// * `count_ones_opt` - An optional hashmap containing the number of ones in each of the
369    /// possible bit vectors of length [`Self::rank`].
370    ///
371    /// # Returns
372    ///
373    /// Returns the integer corresponding to the Lehmer encoding of this permutation.
374    pub fn lehmer_index(&self, count_ones_opt: Option<&HashMap<BitVec<T, Lsb0>, T>>) -> usize
375    where
376        <T as TryFrom<usize>>::Error: fmt::Debug,
377    {
378        let lehmer = self.lehmer(count_ones_opt);
379        let n = self.rank().into() - 1;
380        if n == 0 {
381            0
382        } else {
383            lehmer
384                .into_iter()
385                .enumerate()
386                .map(|(i, l)| {
387                    l.into()
388                        * (n - i).checked_factorial().unwrap_or_else(|| {
389                            panic!("The factorial of `{}` cannot be correctly computed.", n - i)
390                        })
391                })
392                .sum()
393        }
394    }
395}
396
397// =====================
398// Trait implementations
399// =====================
400
401// -------
402// Display
403// -------
404impl<T: PermutationRank + fmt::Display> fmt::Display for Permutation<T> {
405    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
406        write!(
407            f,
408            "π({})",
409            self.image
410                .iter()
411                .map(|i| i.to_string())
412                .collect::<Vec<_>>()
413                .join(".")
414        )
415    }
416}
417
418// ---
419// Mul
420// ---
421impl<T: PermutationRank> Mul<&'_ Permutation<T>> for &Permutation<T>
422where
423    std::ops::Range<T>: Iterator + DoubleEndedIterator,
424    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
425    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
426    <T as TryFrom<usize>>::Error: fmt::Debug,
427    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
428{
429    type Output = Permutation<T>;
430
431    fn mul(self, rhs: &Permutation<T>) -> Self::Output {
432        assert_eq!(
433            self.rank(),
434            rhs.rank(),
435            "The ranks of two multiplying permutations do not match."
436        );
437        Self::Output::builder()
438            .image(
439                rhs.image
440                    .iter()
441                    .map(|&ri| self.image[ri.into()])
442                    .collect::<Vec<T>>(),
443            )
444            .build()
445            .expect("Unable to construct a product `Permutation`.")
446    }
447}
448
449impl<T: PermutationRank> Mul<&'_ Permutation<T>> for Permutation<T>
450where
451    std::ops::Range<T>: Iterator + DoubleEndedIterator,
452    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
453    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
454    <T as TryFrom<usize>>::Error: fmt::Debug,
455    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
456{
457    type Output = Permutation<T>;
458
459    fn mul(self, rhs: &Permutation<T>) -> Self::Output {
460        &self * rhs
461    }
462}
463
464impl<T: PermutationRank> Mul<Permutation<T>> for Permutation<T>
465where
466    std::ops::Range<T>: Iterator + DoubleEndedIterator,
467    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
468    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
469    <T as TryFrom<usize>>::Error: fmt::Debug,
470    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
471{
472    type Output = Permutation<T>;
473
474    fn mul(self, rhs: Permutation<T>) -> Self::Output {
475        &self * &rhs
476    }
477}
478
479impl<T: PermutationRank> Mul<Permutation<T>> for &Permutation<T>
480where
481    std::ops::Range<T>: Iterator + DoubleEndedIterator,
482    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
483    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
484    <T as TryFrom<usize>>::Error: fmt::Debug,
485    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
486{
487    type Output = Permutation<T>;
488
489    fn mul(self, rhs: Permutation<T>) -> Self::Output {
490        self * &rhs
491    }
492}
493
494// ---
495// Inv
496// ---
497impl<T: PermutationRank> Inv for &Permutation<T>
498where
499    std::ops::Range<T>: Iterator + DoubleEndedIterator,
500    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
501    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
502    <T as TryFrom<usize>>::Error: fmt::Debug,
503    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
504{
505    type Output = Permutation<T>;
506
507    fn inv(self) -> Self::Output {
508        let mut image_inv = (T::zero()..self.rank()).collect::<Vec<T>>();
509        image_inv.sort_by_key(|&i| self.image[i.into()]);
510        Self::Output::builder()
511            .image(image_inv)
512            .build()
513            .expect("Unable to construct an inverse `Permutation`.")
514    }
515}
516
517impl<T: PermutationRank> Inv for Permutation<T>
518where
519    std::ops::Range<T>: Iterator + DoubleEndedIterator,
520    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
521    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
522    <T as TryFrom<usize>>::Error: fmt::Debug,
523    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
524{
525    type Output = Permutation<T>;
526
527    fn inv(self) -> Self::Output {
528        (&self).inv()
529    }
530}
531
532// ---
533// Pow
534// ---
535impl<T: PermutationRank> Pow<i32> for &Permutation<T>
536where
537    std::ops::Range<T>: Iterator + DoubleEndedIterator,
538    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
539    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
540    <T as TryFrom<usize>>::Error: fmt::Debug,
541    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
542{
543    type Output = Permutation<T>;
544
545    fn pow(self, rhs: i32) -> Self::Output {
546        if rhs == 0 {
547            Self::Output::builder()
548                .image((T::zero()..self.rank()).collect::<Vec<T>>())
549                .build()
550                .expect("Unable to construct an identity `Permutation`.")
551        } else if rhs > 0 {
552            self * self.pow(rhs - 1)
553        } else {
554            let rhs_p = -rhs;
555            (self * self.pow(rhs_p - 1)).inv()
556        }
557    }
558}
559
560impl<T: PermutationRank> Pow<i32> for Permutation<T>
561where
562    std::ops::Range<T>: Iterator + DoubleEndedIterator,
563    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
564    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
565    <T as TryFrom<usize>>::Error: fmt::Debug,
566    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
567{
568    type Output = Permutation<T>;
569
570    fn pow(self, rhs: i32) -> Self::Output {
571        (&self).pow(rhs)
572    }
573}
574
575// -----------
576// FiniteOrder
577// -----------
578impl<T: PermutationRank + fmt::Display> FiniteOrder for Permutation<T>
579where
580    u32: From<T>,
581    std::ops::Range<T>: Iterator + DoubleEndedIterator,
582    Vec<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
583    VecDeque<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
584    <T as TryFrom<usize>>::Error: fmt::Debug,
585    IndexSet<T>: FromIterator<<std::ops::Range<T> as Iterator>::Item>,
586{
587    type Int = u32;
588
589    /// Calculates the order of this permutation. This is the lowest common multiplier of the
590    /// lengths of the disjoint cycles constituting this permutation.
591    fn order(&self) -> Self::Int {
592        u32::try_from(
593            self.cycle_pattern()
594                .iter()
595                .cloned()
596                .reduce(lcm)
597                .unwrap_or_else(|| {
598                    panic!("Unable to determine the permutation order of `{self}`.")
599                }),
600        )
601        .expect("Unable to convert the permutation order to `u32`.")
602    }
603}
604
605// =========
606// Functions
607// =========
608/// Permutes the items in a vector in-place.
609///
610/// # Arguments
611///
612/// * `vec` - An exclusive reference to a vector of items to be permuted.
613/// * `perm` - A shared reference to a permutation determining how the items are to be permuted.
614pub(crate) fn permute_inplace<T>(vec: &mut Vec<T>, perm: &Permutation<usize>) {
615    assert_eq!(
616        perm.rank(),
617        vec.len(),
618        "The permutation rank does not match the number of items in the vector."
619    );
620    let mut image = perm.image().clone();
621    for idx in 0..vec.len() {
622        if image[idx] != idx {
623            let mut current_idx = idx;
624            loop {
625                let target_idx = image[current_idx];
626                image[current_idx] = current_idx;
627                if image[target_idx] == target_idx {
628                    break;
629                }
630                vec.swap(current_idx, target_idx);
631                current_idx = target_idx;
632            }
633        }
634    }
635}
qsym2/permutation/mod.rs

qsym2/permutation/
mod.rs
