#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use core::fmt;
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Default)]
pub struct Partition(Vec<u32>);
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum PartitionError {
NotWeaklyDecreasing,
ZeroPart,
}
impl crate::memo::HeapSize for Partition {
fn heap_bytes(&self) -> usize {
self.0.capacity() * std::mem::size_of::<u32>()
}
}
impl Partition {
pub fn new<I: IntoIterator<Item = u32>>(parts: I) -> Self {
let mut v: Vec<u32> = parts.into_iter().filter(|&x| x != 0).collect();
v.sort_unstable_by(|a, b| b.cmp(a));
Partition(v)
}
pub fn try_new<I: IntoIterator<Item = u32>>(parts: I) -> Result<Self, PartitionError> {
let v: Vec<u32> = parts.into_iter().collect();
for w in v.windows(2) {
if w[0] < w[1] {
return Err(PartitionError::NotWeaklyDecreasing);
}
}
if v.contains(&0) {
return Err(PartitionError::ZeroPart);
}
Ok(Partition(v))
}
pub(crate) fn from_sorted(v: Vec<u32>) -> Self {
debug_assert!(v.windows(2).all(|w| w[0] >= w[1]) && v.iter().all(|&x| x != 0));
Partition(v)
}
#[inline]
pub fn parts(&self) -> &[u32] {
&self.0
}
#[inline]
pub fn len(&self) -> usize {
self.0.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
#[inline]
pub fn size(&self) -> u32 {
self.0.iter().sum()
}
#[inline]
pub fn part(&self, i: usize) -> u32 {
self.0.get(i).copied().unwrap_or(0)
}
pub fn contains(&self, other: &Partition) -> bool {
(0..other.len()).all(|i| self.part(i) >= other.part(i))
}
pub fn conjugate(&self) -> Partition {
Partition::from_sorted(conjugate_parts(&self.0))
}
pub fn beta_numbers(&self, rows: usize) -> Vec<u32> {
assert!(
rows >= self.len(),
"an abacus needs at least ℓ(λ) beads to hold λ"
);
(0..rows)
.map(|j| self.part(j) + (rows - 1 - j) as u32)
.collect()
}
pub fn from_beta_numbers(beta: &[u32]) -> Partition {
debug_assert!(
beta.windows(2).all(|w| w[0] > w[1]),
"β-numbers must be strictly decreasing"
);
let l = beta.len();
let parts: Vec<u32> = (0..l)
.map(|j| beta[j] - (l - 1 - j) as u32)
.filter(|&x| x > 0)
.collect();
Partition::from_sorted(parts)
}
fn k_rows(&self, k: u32) -> usize {
let k = k as usize;
let l = self.len().max(1);
k * ((l + k) / k)
}
pub fn k_core(&self, k: u32) -> Partition {
assert!(k >= 1, "a k-core needs k ≥ 1");
let rows = self.k_rows(k);
let beta = self.beta_numbers(rows);
let mut counts = vec![0usize; k as usize];
for &b in &beta {
counts[(b % k) as usize] += 1;
}
let mut packed: Vec<u32> = Vec::with_capacity(rows);
for (r, &c) in counts.iter().enumerate() {
for p in 0..c {
packed.push(k * p as u32 + r as u32);
}
}
packed.sort_unstable_by(|a, b| b.cmp(a));
Partition::from_beta_numbers(&packed)
}
pub fn k_quotient(&self, k: u32) -> Vec<Partition> {
assert!(k >= 1, "a k-quotient needs k ≥ 1");
let rows = self.k_rows(k);
let beta = self.beta_numbers(rows);
(0..k)
.map(|r| {
let mut pos: Vec<u32> = beta
.iter()
.filter(|&&b| b % k == r)
.map(|&b| b / k)
.collect();
pos.sort_unstable_by(|a, b| b.cmp(a));
Partition::from_beta_numbers(&pos)
})
.collect()
}
pub fn has_empty_k_core(&self, k: u32) -> bool {
self.k_core(k).is_empty()
}
pub fn z(&self) -> u128 {
self.try_z()
.unwrap_or_else(|| panic!("z_{self} does not fit u128; use try_z, z_in or div_by_z"))
}
pub fn try_z(&self) -> Option<u128> {
let mut result: Option<u128> = Some(1);
self.for_each_part_multiplicity(|val, mult| {
result = result.and_then(|r| {
let mut r = r.checked_mul(u128::from(val).checked_pow(mult)?)?;
for k in 2..=u128::from(mult) {
r = r.checked_mul(k)?;
}
Some(r)
});
});
result
}
pub fn z_in<C: crate::coeff::Ring>(&self) -> C {
let mut result = C::one();
self.for_each_part_multiplicity(|val, mult| {
for _ in 0..mult {
result = result.mul(&C::from_u128(val as u128));
}
for k in 2..=mult as u128 {
result = result.mul(&C::from_u128(k));
}
});
result
}
pub fn div_by_z<C: crate::coeff::QAlgebra>(&self, x: &C) -> C {
let mut out = x.clone();
self.for_each_part_multiplicity(|val, mult| {
for _ in 0..mult {
out = out.div_u128(val as u128);
}
for k in 2..=mult as u128 {
out = out.div_u128(k);
}
});
out
}
fn for_each_part_multiplicity(&self, mut f: impl FnMut(u32, u32)) {
let mut i = 0;
while i < self.0.len() {
let val = self.0[i];
let mut mult = 0u32;
while i < self.0.len() && self.0[i] == val {
mult += 1;
i += 1;
}
f(val, mult);
}
}
pub fn part_multiplicities(&self) -> Vec<(u32, u32)> {
let mut out = Vec::new();
self.for_each_part_multiplicity(|val, mult| out.push((val, mult)));
out
}
}
pub(crate) fn conjugate_parts(parts: &[u32]) -> Vec<u32> {
let Some(&width) = parts.first() else {
return Vec::new();
};
let mut conj = vec![0u32; width as usize];
for &p in parts {
for c in conj.iter_mut().take(p as usize) {
*c += 1;
}
}
conj
}
impl fmt::Display for Partition {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str("[")?;
for (i, p) in self.0.iter().enumerate() {
if i > 0 {
f.write_str(",")?;
}
write!(f, "{p}")?;
}
f.write_str("]")
}
}
pub fn partitions_of(n: u32) -> Vec<Partition> {
fn rec(n: u32, max: u32, cur: &mut Vec<u32>, out: &mut Vec<Partition>) {
if n == 0 {
out.push(Partition::from_sorted(cur.clone()));
return;
}
let hi = n.min(max);
for k in (1..=hi).rev() {
cur.push(k);
rec(n - k, k, cur, out);
cur.pop();
}
}
let mut out = Vec::new();
let mut cur = Vec::new();
rec(n, n.max(1), &mut cur, &mut out);
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn normalizes() {
let p = Partition::new([1, 3, 0, 2, 2]);
assert_eq!(p.parts(), &[3, 2, 2, 1]);
assert_eq!(p.size(), 8);
assert_eq!(p.len(), 4);
}
#[test]
fn strict_validation() {
assert!(Partition::try_new([3, 2, 2, 1]).is_ok());
assert_eq!(
Partition::try_new([2, 3]),
Err(PartitionError::NotWeaklyDecreasing)
);
assert_eq!(Partition::try_new([2, 1, 0]), Err(PartitionError::ZeroPart));
}
#[test]
fn containment() {
let lam = Partition::new([3, 2, 1]);
let mu = Partition::new([2, 1]);
assert!(lam.contains(&mu));
assert!(!mu.contains(&lam));
assert!(lam.contains(&Partition::default())); }
#[test]
fn conjugate_is_involutive_and_correct() {
assert_eq!(Partition::new([3, 1]).conjugate().parts(), &[2, 1, 1]);
assert_eq!(Partition::new([4, 2, 1]).conjugate().parts(), &[3, 2, 1, 1]);
for parts in [&[3, 1][..], &[4, 2, 1], &[2, 2], &[5]] {
let p = Partition::new(parts.iter().copied());
assert_eq!(p.conjugate().conjugate(), p);
}
assert_eq!(Partition::default().conjugate(), Partition::default());
}
#[test]
fn centralizer_order_z() {
assert_eq!(Partition::new([2, 1, 1]).z(), 4); assert_eq!(Partition::new([1, 1]).z(), 2);
assert_eq!(Partition::new([2, 2]).z(), 8); assert_eq!(Partition::new([3]).z(), 3);
assert_eq!(Partition::default().z(), 1);
}
#[test]
fn z_in_and_div_by_z_agree_with_z() {
use crate::coeff::QAlgebra;
for n in 0..=12u32 {
for lambda in crate::memo::partitions_cached(n).iter() {
let z = lambda.z();
assert_eq!(lambda.z_in::<i128>(), z as i128, "z_in at {lambda}");
let x = crate::coeff::Rational::new(360_360, 1);
assert_eq!(lambda.div_by_z(&x), x.div_u128(z), "div_by_z at {lambda}");
}
}
}
#[test]
#[cfg(feature = "bignum")]
fn z_in_is_exact_past_the_u128_ceiling() {
use core::str::FromStr;
use num_bigint::BigInt;
let ones = Partition::new(vec![1; 40]);
let forty_factorial =
BigInt::from_str("815915283247897734345611269596115894272000000000").unwrap();
assert_eq!(ones.z_in::<BigInt>(), forty_factorial);
let mixed = Partition::new(vec![3, 3, 3, 1, 1]);
assert_eq!(mixed.z_in::<BigInt>(), BigInt::from(mixed.z()));
}
#[test]
#[cfg(feature = "bignum")]
fn s_to_p_is_exact_past_the_u128_ceiling() {
use crate::coeff::Ring;
use crate::convert::FromSchur;
use crate::sym::{PowerSum, Schur, SymFn};
use num_bigint::BigInt;
use num_rational::BigRational;
let lambda = Partition::new(vec![36, 3, 1]);
let s: Schur<BigRational> = Schur::monomial(lambda.clone(), BigRational::one());
let p = PowerSum::from_schur(&s);
for mu in [
Partition::new(vec![1; 40]),
Partition::new(vec![2; 20]),
Partition::new(vec![20, 10, 5, 5]),
] {
let chi: BigInt = crate::character::character_in(&lambda, &mu);
let want = BigRational::new(chi, mu.z_in::<BigInt>());
assert_eq!(p.coeff(&mu), want, "⟨s_{lambda}, p_{mu}⟩");
}
}
#[test]
fn beta_numbers_round_trip_at_every_padding() {
for parts in [&[3, 1][..], &[4, 2, 1], &[2, 2], &[5], &[]] {
let p = Partition::new(parts.iter().copied());
for extra in 0..4 {
let rows = p.len() + extra;
let beta = p.beta_numbers(rows);
assert!(
beta.windows(2).all(|w| w[0] > w[1]),
"β strictly decreasing"
);
assert_eq!(
Partition::from_beta_numbers(&beta),
p,
"{p} at {rows} beads"
);
}
}
}
#[test]
fn core_and_quotient_split_the_size() {
for n in 0..=9u32 {
for lambda in partitions_of(n) {
for k in 1..=4u32 {
let core = lambda.k_core(k);
let quot: u32 = lambda.k_quotient(k).iter().map(Partition::size).sum();
assert_eq!(
core.size() + k * quot,
n,
"Littlewood decomposition of {lambda} at k={k}"
);
assert_eq!(core.k_core(k), core, "{lambda} core is a fixed point");
}
}
}
}
#[test]
fn k_quotient_is_independent_of_the_padding() {
for n in 0..=8u32 {
for lambda in partitions_of(n) {
for k in 1..=4u32 {
let want = lambda.k_quotient(k);
for extra in 1..=3usize {
let rows = lambda.len().max(1);
let rows =
k as usize * ((rows + k as usize) / k as usize) + extra * k as usize;
let beta = lambda.beta_numbers(rows);
let got: Vec<Partition> = (0..k)
.map(|r| {
let mut pos: Vec<u32> = beta
.iter()
.filter(|&&b| b % k == r)
.map(|&b| b / k)
.collect();
pos.sort_unstable_by(|a, b| b.cmp(a));
Partition::from_beta_numbers(&pos)
})
.collect();
assert_eq!(got, want, "{lambda} at k={k}, {rows} beads");
}
}
}
}
}
#[test]
fn one_cores_are_empty() {
for n in 0..=7u32 {
for lambda in partitions_of(n) {
assert!(lambda.has_empty_k_core(1), "{lambda}");
assert_eq!(lambda.k_quotient(1), vec![lambda.clone()]);
}
}
}
#[test]
fn partition_counts() {
let expected = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42];
for (n, &e) in expected.iter().enumerate() {
assert_eq!(partitions_of(n as u32).len(), e, "p({n})");
}
}
}