#[derive(Debug, Clone, PartialEq)]
pub struct Permutation {
map: Vec<usize>,
inv: Vec<usize>,
}
impl PartialOrd for Permutation {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.map.partial_cmp(&other.map)
}
}
impl Permutation {
pub fn apply_slice<T: Clone, S>(&self, slice: S) -> Vec<T>
where
S: AsRef<[T]>,
{
let s = slice.as_ref();
self.map.iter().map(|&idx| s[idx].clone()).collect()
}
pub fn inverse(&self) -> Self {
Permutation {
map: self.inv.clone(),
inv: self.map.clone(),
}
}
pub fn id(n: usize) -> Self {
Permutation {
map: (0..n).collect(),
inv: (0..n).collect(),
}
}
pub fn sort<T, S>(slice: S) -> Permutation
where
T: Ord,
S: AsRef<[T]>,
{
let s = slice.as_ref();
let mut permutation: Vec<usize> = (0..s.len()).collect();
permutation.sort_by_key(|&i| &s[i]);
Self::from_map(permutation)
}
pub fn apply_slice_inv<T: Clone, S>(&self, slice: S) -> Vec<T>
where
S: AsRef<[T]>,
{
let s = slice.as_ref();
self.inv.iter().map(|&idx| s[idx].clone()).collect()
}
pub fn find_cycles(&self) -> Vec<Vec<usize>> {
let mut visited = vec![false; self.map.len()];
let mut cycles = Vec::new();
for i in 0..self.map.len() {
if visited[i] {
continue;
}
let mut cycle = Vec::new();
let mut j = i;
while !visited[j] {
visited[j] = true;
cycle.push(j);
j = self.map[j];
}
if !cycle.is_empty() {
cycles.push(cycle);
}
}
cycles
}
fn cycle_to_transpositions(cycle: &[usize]) -> Vec<(usize, usize)> {
let mut transpositions = Vec::new();
for i in (1..cycle.len()).rev() {
transpositions.push((cycle[0], cycle[i]));
}
transpositions
}
pub fn transpositions(&self) -> Vec<(usize, usize)> {
let cycles = self.find_cycles();
let mut transpositions = Vec::new();
for cycle in cycles {
transpositions.extend(Self::cycle_to_transpositions(&cycle));
}
transpositions
}
pub fn apply_slice_in_place_inv<T: Clone, S>(&self, slice: &mut S)
where
S: AsMut<[T]>,
{
let transpositions = self.transpositions();
for (i, j) in transpositions {
slice.as_mut().swap(i, j);
}
}
pub fn apply_slice_in_place<T: Clone, S>(&self, slice: &mut S)
where
S: AsMut<[T]>,
{
let transpositions = self.transpositions();
for (i, j) in transpositions.iter().rev() {
slice.as_mut().swap(*i, *j);
}
}
pub fn from_map(map: Vec<usize>) -> Self {
let mut inv = vec![0; map.len()];
for (i, &j) in map.iter().enumerate() {
inv[j] = i;
}
Permutation { map, inv }
}
pub fn myrvold_ruskey_rank1(mut self) -> usize {
let n = self.map.len();
if self.map.len() == 1 {
return 0;
}
let s = self.map[n - 1];
self.map.swap_remove(self.inv[n - 1]);
self.inv.swap_remove(s);
s + n * self.myrvold_ruskey_rank1()
}
pub fn myrvold_ruskey_unrank1(n: usize, mut rank: usize) -> Self {
let mut p = (0..n).collect::<Vec<_>>();
for i in (1..=n).rev() {
let j = rank % i;
rank /= i;
p.swap(i - 1, j);
}
Permutation::from_map(p)
}
pub fn myrvold_ruskey_rank2(mut self) -> usize {
let n = self.map.len();
if n == 1 {
return 0;
}
let s = self.map[n - 1];
self.map.swap_remove(self.inv[n - 1]);
self.inv.swap_remove(s);
s * Self::factorial(n - 1) + self.myrvold_ruskey_rank2()
}
fn factorial(n: usize) -> usize {
(1..=n).product()
}
pub fn myrvold_ruskey_unrank2(n: usize, mut rank: usize) -> Self {
let mut p = (0..n).collect::<Vec<_>>();
for i in (1..=n).rev() {
let s = rank / (Self::factorial(i - 1));
p.swap(i - 1, s);
rank %= Self::factorial(i - 1);
}
Permutation::from_map(p)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_myrvold_ruskey_rank1() {
let p = Permutation::from_map(vec![2, 1, 3, 0]);
assert_eq!(p.myrvold_ruskey_rank1(), 12);
for i in 0..=23 {
assert_eq!(
i,
Permutation::myrvold_ruskey_rank1(Permutation::myrvold_ruskey_unrank1(4, i))
);
}
}
#[test]
fn test_myrvold_ruskey_rank2() {
let p = Permutation::myrvold_ruskey_unrank2(4, 1);
assert_eq!(p.map, vec![2, 1, 3, 0]);
for i in 0..=23 {
assert_eq!(
i,
Permutation::myrvold_ruskey_rank2(Permutation::myrvold_ruskey_unrank2(4, i))
);
}
}
#[test]
fn test_apply_slice() {
let p = Permutation::from_map(vec![2, 1, 3, 0]);
let data = vec![10, 20, 30, 40];
let permuted = p.apply_slice(data);
assert_eq!(permuted, vec![30, 20, 40, 10]);
}
#[test]
fn test_apply_slice_inv() {
let p = Permutation::from_map(vec![2, 1, 3, 0]);
let data = vec![10, 20, 30, 40];
let permuted = p.apply_slice_inv(data);
assert_eq!(permuted, vec![40, 20, 10, 30]);
}
#[test]
fn test_find_cycles() {
let p = Permutation::from_map(vec![2, 0, 1, 3]);
let cycles = p.find_cycles();
assert_eq!(cycles, vec![vec![0, 2, 1], vec![3]]);
}
#[test]
fn test_cycle_to_transpositions() {
let cycle = vec![0, 2, 1];
let transpositions = Permutation::cycle_to_transpositions(&cycle);
assert_eq!(transpositions, vec![(0, 1), (0, 2)]);
}
#[test]
fn test_transpositions() {
let p = Permutation::from_map(vec![2, 0, 1, 3]);
let transpositions = p.transpositions();
assert_eq!(transpositions, vec![(0, 1), (0, 2)]);
}
#[test]
fn test_apply_slice_in_place() {
let p = Permutation::from_map(vec![2, 0, 1, 3]);
let mut data = vec![10, 20, 30, 40];
p.apply_slice_in_place(&mut data);
assert_eq!(data, vec![20, 30, 10, 40]);
}
#[test]
fn test_apply_slice_in_place_inv() {
let p = Permutation::from_map(vec![2, 0, 1, 3]);
let mut data = vec![10, 20, 30, 40];
p.apply_slice_in_place_inv(&mut data);
assert_eq!(data, vec![30, 10, 20, 40]);
}
#[test]
fn test_sort() {
let data = vec![30, 10, 20, 40];
let perm = Permutation::sort(&data);
assert_eq!(perm.map, vec![1, 2, 0, 3]);
let sorted_data = perm.apply_slice(&data);
assert_eq!(sorted_data, vec![10, 20, 30, 40]);
}
#[test]
fn test_sort_inverse() {
let data = vec![30, 10, 20, 40];
let perm = Permutation::sort(&data);
let sorted_data = perm.apply_slice(&data);
assert_eq!(sorted_data, vec![10, 20, 30, 40]);
let inv_perm = perm.inverse();
let original_data = inv_perm.apply_slice(&sorted_data);
assert_eq!(original_data, data);
}
}