#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use core::fmt;
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
pub struct Perm {
data: [u8; MAX_SUPPORT],
len: u8,
}
pub const MAX_SUPPORT: usize = 32;
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum PermError {
ZeroValue,
NotABijection,
TooLarge,
}
impl Perm {
pub fn identity() -> Self {
Perm {
data: [0; MAX_SUPPORT],
len: 0,
}
}
#[inline]
fn slice(&self) -> &[u8] {
&self.data[..self.len as usize]
}
#[inline]
fn from_array(mut data: [u8; MAX_SUPPORT], mut len: usize) -> Self {
while len > 0 && data[len - 1] as usize == len {
len -= 1;
}
for slot in data.iter_mut().skip(len) {
*slot = 0;
}
Perm {
data,
len: len as u8,
}
}
pub fn new<I: IntoIterator<Item = u32>>(one_line: I) -> Result<Self, PermError> {
let v: Vec<u32> = one_line.into_iter().collect();
let n = v.len();
if n > MAX_SUPPORT {
return Err(PermError::TooLarge);
}
let mut seen = vec![false; n + 1];
for &x in &v {
if x == 0 {
return Err(PermError::ZeroValue);
}
let x = x as usize;
if x > n || seen[x] {
return Err(PermError::NotABijection);
}
seen[x] = true;
}
Ok(Perm::from_valid(v))
}
pub(crate) fn from_valid(v: Vec<u32>) -> Self {
assert!(v.len() <= MAX_SUPPORT, "permutation exceeds MAX_SUPPORT");
let mut data = [0u8; MAX_SUPPORT];
for (slot, &x) in data.iter_mut().zip(v.iter()) {
*slot = x as u8;
}
Perm::from_array(data, v.len())
}
#[inline]
pub fn at(&self, i: u32) -> u32 {
assert!(i >= 1, "positions are 1-based; w(0) names no cell");
match self.slice().get((i - 1) as usize) {
Some(&x) => x as u32,
None => i,
}
}
#[inline]
pub fn one_line(&self) -> &[u8] {
self.slice()
}
#[inline]
pub fn support_len(&self) -> u32 {
self.len as u32
}
#[inline]
pub fn is_identity(&self) -> bool {
self.len == 0
}
pub fn padded(&self, n: u32) -> Vec<u32> {
(1..=n.max(self.support_len()))
.map(|i| self.at(i))
.collect()
}
pub fn length(&self) -> u32 {
let v = self.slice();
let mut n = 0;
for i in 0..v.len() {
for j in (i + 1)..v.len() {
if v[i] > v[j] {
n += 1;
}
}
}
n
}
pub fn code(&self) -> Vec<u32> {
let v = self.slice();
let mut c = vec![0u32; v.len()];
for i in 0..v.len() {
for j in (i + 1)..v.len() {
if v[j] < v[i] {
c[i] += 1;
}
}
}
while c.last() == Some(&0) {
c.pop();
}
c
}
pub fn from_code(code: &[u32]) -> Self {
let mut m = code.len() as u32;
for (i, &c) in code.iter().enumerate() {
m = m.max((i as u32) + 1 + c);
}
let mut avail: Vec<u32> = (1..=m).collect();
let mut out = Vec::with_capacity(m as usize);
for i in 0..m as usize {
let c = code.get(i).copied().unwrap_or(0) as usize;
out.push(avail.remove(c));
}
Perm::from_valid(out)
}
pub fn descents(&self) -> Vec<u32> {
let v = self.slice();
(1..v.len())
.filter(|&i| v[i - 1] > v[i])
.map(|i| i as u32)
.collect()
}
#[inline]
pub fn last_descent(&self) -> Option<u32> {
let v = self.slice();
(1..v.len())
.rev()
.find(|&i| v[i - 1] > v[i])
.map(|i| i as u32)
}
#[inline]
pub fn for_each_cover_left(&self, i: u32, mut f: impl FnMut(u32, Perm)) {
let n = self.support_len().max(i) as usize;
debug_assert!(n <= MAX_SUPPORT);
let mut base = [0u8; MAX_SUPPORT];
for (k, slot) in base.iter_mut().enumerate().take(n) {
*slot = self.at(k as u32 + 1) as u8;
}
let wi = base[(i - 1) as usize];
let mut running_max = 0u8;
for j in (1..i as usize).rev() {
let wj = base[j - 1];
if wj < wi && wj > running_max {
running_max = wj;
let mut u = base;
u.swap((i - 1) as usize, j - 1);
f(j as u32, Perm::from_array(u, n));
}
}
}
pub fn is_dominant(&self) -> bool {
self.code().windows(2).all(|w| w[0] >= w[1])
}
pub fn is_grassmannian(&self) -> Option<u32> {
let d = self.descents();
match d.len() {
0 => Some(0),
1 => Some(d[0]),
_ => None,
}
}
pub fn inverse(&self) -> Self {
let v = self.slice();
let mut data = [0u8; MAX_SUPPORT];
for (i, &x) in v.iter().enumerate() {
data[(x - 1) as usize] = (i + 1) as u8;
}
Perm::from_array(data, v.len())
}
pub fn transpose(&self, i: u32, j: u32) -> Self {
assert!(
i >= 1 && j >= 1,
"positions are 1-based; t_{{0j}} names no cell"
);
let n = i.max(j).max(self.support_len()) as usize;
assert!(n <= MAX_SUPPORT, "transposition exceeds MAX_SUPPORT");
let mut data = [0u8; MAX_SUPPORT];
for (k, slot) in data.iter_mut().enumerate().take(n) {
*slot = self.at(k as u32 + 1) as u8;
}
data.swap((i - 1) as usize, (j - 1) as usize);
Perm::from_array(data, n)
}
pub fn covers_right(&self, i: u32) -> Vec<(u32, Perm)> {
assert!(i >= 1, "positions are 1-based; w(0) names no cell");
let n = (self.support_len().max(i) + 1) as usize;
assert!(n <= MAX_SUPPORT, "cover scan exceeds MAX_SUPPORT");
let mut base = [0u8; MAX_SUPPORT];
for (k, slot) in base.iter_mut().enumerate().take(n) {
*slot = self.at(k as u32 + 1) as u8;
}
let wi = base[(i - 1) as usize];
let mut out = Vec::new();
let mut running_min = u8::MAX;
for j in (i as usize + 1)..=n {
let wj = base[j - 1];
if wj > wi && wj < running_min {
running_min = wj;
let mut u = base;
u.swap((i - 1) as usize, j - 1);
out.push((j as u32, Perm::from_array(u, n)));
}
}
out
}
pub fn covers_left(&self, i: u32) -> Vec<(u32, Perm)> {
assert!(i >= 1, "positions are 1-based; w(0) names no cell");
let n = self.support_len().max(i) as usize;
assert!(n <= MAX_SUPPORT, "cover scan exceeds MAX_SUPPORT");
let mut base = [0u8; MAX_SUPPORT];
for (k, slot) in base.iter_mut().enumerate().take(n) {
*slot = self.at(k as u32 + 1) as u8;
}
let wi = base[(i - 1) as usize];
let mut out = Vec::new();
let mut running_max = 0u8;
for j in (1..i as usize).rev() {
let wj = base[j - 1];
if wj < wi && wj > running_max {
running_max = wj;
let mut u = base;
u.swap((i - 1) as usize, j - 1);
out.push((j as u32, Perm::from_array(u, n)));
}
}
out
}
pub fn bruhat_le(&self, other: &Perm) -> bool {
let n = self.support_len().max(other.support_len()) as usize;
let (mut a, mut b) = ([0u8; MAX_SUPPORT], [0u8; MAX_SUPPORT]);
for i in 0..n {
let (x, y) = (self.at(i as u32 + 1) as u8, other.at(i as u32 + 1) as u8);
let mut j = i;
while j > 0 && a[j - 1] > x {
a[j] = a[j - 1];
j -= 1;
}
a[j] = x;
let mut j = i;
while j > 0 && b[j - 1] > y {
b[j] = b[j - 1];
j -= 1;
}
b[j] = y;
for k in 0..=i {
if a[k] > b[k] {
return false;
}
}
}
true
}
pub fn reduced_word(&self) -> Vec<u32> {
let mut v = self.slice().to_vec();
let mut word = Vec::new();
while let Some(i) = (1..v.len()).find(|&i| v[i - 1] > v[i]) {
v.swap(i - 1, i);
word.push(i as u32);
}
debug_assert_eq!(word.len() as u32, self.length());
word.reverse();
word
}
pub fn transition(&self) -> Option<(u32, Perm, Vec<Perm>)> {
let r = self.last_descent()?;
let wr = self.at(r);
let s = (r + 1..=self.support_len()).rfind(|&s| self.at(s) < wr)?;
let v = self.transpose(r, s);
debug_assert_eq!(v.length() + 1, self.length());
let ups = v.covers_left(r).into_iter().map(|(_, p)| p).collect();
Some((r, v, ups))
}
}
impl fmt::Display for Perm {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if self.is_identity() {
return write!(f, "id");
}
write!(f, "[")?;
for (i, x) in self.slice().iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
write!(f, "{x}")?;
}
write!(f, "]")
}
}
#[cfg(test)]
pub(crate) mod tests {
use super::*;
fn p(v: &[u32]) -> Perm {
Perm::new(v.iter().copied()).unwrap()
}
#[test]
fn strips_trailing_fixed_points() {
assert_eq!(p(&[2, 1]), p(&[2, 1, 3]));
assert_eq!(p(&[2, 1]), p(&[2, 1, 3, 4, 5]));
assert_eq!(p(&[1, 2, 3]), Perm::identity());
assert!(p(&[1, 2, 3]).is_identity());
assert_eq!(p(&[3, 2, 1]).one_line(), &[3, 2, 1]);
}
#[test]
fn rejects_non_permutations() {
assert_eq!(Perm::new([1, 1]), Err(PermError::NotABijection));
assert_eq!(Perm::new([0, 1]), Err(PermError::ZeroValue));
assert_eq!(Perm::new([1, 3]), Err(PermError::NotABijection));
}
#[test]
fn at_is_one_based_and_total() {
let w = p(&[2, 1]);
assert_eq!(w.at(1), 2);
assert_eq!(w.at(2), 1);
assert_eq!(w.at(3), 3);
assert_eq!(w.at(97), 97);
}
#[test]
fn length_and_code_agree() {
for n in 0..=6u32 {
for w in all_perms(n) {
assert_eq!(w.code().iter().sum::<u32>(), w.length(), "{w}");
}
}
}
#[test]
fn code_round_trips() {
for n in 0..=7u32 {
for w in all_perms(n) {
assert_eq!(Perm::from_code(&w.code()), w, "{w}");
}
}
}
#[test]
fn code_round_trips_through_padding() {
let w = p(&[1, 4, 2, 3]);
let mut c = w.code();
c.extend_from_slice(&[0, 0, 0]);
assert_eq!(Perm::from_code(&c), w);
}
#[test]
fn inverse_is_an_involution() {
for n in 0..=6u32 {
for w in all_perms(n) {
assert_eq!(w.inverse().inverse(), w, "{w}");
assert_eq!(w.inverse().length(), w.length(), "{w}");
for i in 1..=n {
assert_eq!(w.inverse().at(w.at(i)), i, "{w} at {i}");
}
}
}
}
#[test]
fn dominant_and_grassmannian_families() {
assert!(p(&[3, 2, 1]).is_dominant()); assert!(!p(&[1, 4, 2, 3]).is_dominant()); assert_eq!(p(&[1, 3, 2]).is_grassmannian(), Some(2));
assert_eq!(p(&[2, 4, 1, 3]).is_grassmannian(), Some(2));
assert_eq!(p(&[2, 1, 4, 3]).is_grassmannian(), None);
assert_eq!(Perm::identity().is_grassmannian(), Some(0));
for n in 2..=7u32 {
let w0: Vec<u32> = (1..=n).rev().collect();
assert!(p(&w0).is_dominant());
assert_eq!(p(&w0).length(), n * (n - 1) / 2);
}
}
#[test]
fn covers_really_are_covers() {
for n in 0..=6u32 {
for w in all_perms(n) {
for i in 1..=(n + 1) {
for (_, u) in w.covers_right(i) {
assert_eq!(u.length(), w.length() + 1, "{w} right {i} -> {u}");
}
for (_, u) in w.covers_left(i) {
assert_eq!(u.length(), w.length() + 1, "{w} left {i} -> {u}");
}
}
}
}
}
#[test]
fn cover_scans_are_exhaustive_against_brute_force() {
for n in 0..=5u32 {
for w in all_perms(n) {
for i in 1..=(n + 1) {
let bound = n + 4;
let mut want_r: Vec<Perm> = Vec::new();
for j in (i + 1)..=bound {
let u = w.transpose(i, j);
if u.length() == w.length() + 1 {
want_r.push(u);
}
}
let got_r: Vec<Perm> = w.covers_right(i).into_iter().map(|x| x.1).collect();
assert_eq!(got_r, want_r, "right covers of {w} at {i}");
let mut want_l: Vec<Perm> = Vec::new();
for j in (1..i).rev() {
let u = w.transpose(j, i);
if u.length() == w.length() + 1 {
want_l.push(u);
}
}
let got_l: Vec<Perm> = w.covers_left(i).into_iter().map(|x| x.1).collect();
assert_eq!(got_l, want_l, "left covers of {w} at {i}");
}
}
}
}
#[test]
fn transition_drops_length_by_one() {
for n in 0..=6u32 {
for w in all_perms(n) {
match w.transition() {
None => assert!(w.is_identity(), "{w}"),
Some((r, v, ups)) => {
assert_eq!(v.length() + 1, w.length(), "{w}");
assert!(r >= 1);
for u in &ups {
assert_eq!(u.length(), v.length() + 1, "{w} -> {u}");
}
}
}
}
}
}
pub(crate) fn all_perms(n: u32) -> Vec<Perm> {
let mut out = Vec::new();
let mut cur: Vec<u32> = (1..=n).collect();
permute(&mut cur, 0, &mut out);
out
}
fn permute(cur: &mut Vec<u32>, k: usize, out: &mut Vec<Perm>) {
if k == cur.len() {
out.push(Perm::new(cur.iter().copied()).unwrap());
return;
}
for i in k..cur.len() {
cur.swap(k, i);
permute(cur, k + 1, out);
cur.swap(k, i);
}
}
}