#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::HashMap;
use crate::coeff::Ring;
use crate::convert::{beta_mask, pieri_trie, unit_mask_layer, MASK_LIMIT};
use crate::fasthash::Map;
use crate::memo::kostka_cached;
use crate::partition::Partition;
pub fn kostka(lambda: &Partition, mu: &Partition) -> u128 {
try_kostka(lambda, mu)
.unwrap_or_else(|| panic!("K_{{{lambda},{mu}}} does not fit u128; use try_kostka"))
}
pub fn try_kostka(lambda: &Partition, mu: &Partition) -> Option<u128> {
if lambda.size() != mu.size() {
return Some(0);
}
if lambda.is_empty() {
return Some(1); }
if !dominates(lambda, mu) {
return Some(0);
}
kostka_cached(lambda, mu, || kostka_uncached(lambda, mu))
}
pub(crate) fn dominates(lambda: &Partition, mu: &Partition) -> bool {
let (mut a, mut b) = (0u32, 0u32);
for i in 0..lambda.len().max(mu.len()) {
a += lambda.part(i);
b += mu.part(i);
if a < b {
return false;
}
}
true
}
fn kostka_uncached(lambda: &Partition, mu: &Partition) -> Option<u128> {
if mu.is_empty() {
return Some(0);
}
let bound = lambda.parts();
let mut cur: HashMap<Vec<u32>, u128> = HashMap::new();
cur.insert(Vec::new(), 1);
let mut next: HashMap<Vec<u32>, u128> = HashMap::new();
let mut buf: Vec<u32> = Vec::new();
let mut overflowed = false;
for &r in mu.parts() {
next.clear();
for (shape, &ways) in cur.iter() {
buf.clear();
buf.extend_from_slice(shape);
buf.resize(bound.len(), 0);
grow(0, r, u32::MAX, &mut buf, bound, &mut |grown: &[u32]| {
let end = grown.iter().rposition(|&x| x > 0).map_or(0, |i| i + 1);
let slot = next.entry(grown[..end].to_vec()).or_insert(0);
match slot.checked_add(ways) {
Some(sum) => *slot = sum,
None => overflowed = true,
}
});
}
if overflowed {
return None;
}
std::mem::swap(&mut cur, &mut next);
if cur.is_empty() {
return Some(0);
}
}
Some(cur.get(bound).copied().unwrap_or(0))
}
fn grow(
i: usize,
left: u32,
prev_old: u32,
shape: &mut Vec<u32>,
bound: &[u32],
emit: &mut impl FnMut(&[u32]),
) {
if i == shape.len() {
if left == 0 {
emit(shape);
}
return;
}
let capacity: u32 = bound[i..]
.iter()
.zip(shape[i..].iter())
.map(|(b, s)| b.saturating_sub(*s))
.sum();
if capacity < left {
return;
}
let old = shape[i];
let hi = prev_old.min(bound[i]).min(old + left);
if hi < old {
return;
}
for v in old..=hi {
shape[i] = v;
grow(i + 1, left - (v - old), old, shape, bound, emit);
}
shape[i] = old;
}
pub fn semistandard_tableaux(lambda: &Partition, weight: &[u32]) -> Vec<Vec<Vec<u32>>> {
if u64::from(lambda.size()) != weight.iter().map(|&x| u64::from(x)).sum::<u64>() {
return Vec::new();
}
if lambda.is_empty() {
return vec![Vec::new()];
}
let mut chain: Vec<Vec<u32>> = vec![vec![0u32; lambda.len()]];
let mut out = Vec::new();
chains(lambda, weight, &mut chain, &mut out);
out.sort_by_key(|a| reading_word(a));
out
}
fn reading_word(t: &[Vec<u32>]) -> Vec<u32> {
t.concat()
}
fn chains(
lambda: &Partition,
left: &[u32],
chain: &mut Vec<Vec<u32>>,
out: &mut Vec<Vec<Vec<u32>>>,
) {
let Some((&r, rest)) = left.split_first() else {
out.push(tableau_of(chain));
return;
};
let mut buf = chain
.last()
.expect("the chain starts at the empty shape")
.clone();
grow(0, r, u32::MAX, &mut buf, lambda.parts(), &mut |grown| {
let k = rest.len();
for j in 0..lambda.len() {
let need = if j + k < lambda.len() {
lambda.part(j + k)
} else {
0
};
if grown[j] < need {
return;
}
}
chain.push(grown.to_vec());
chains(lambda, rest, chain, out);
chain.pop();
});
}
fn tableau_of(chain: &[Vec<u32>]) -> Vec<Vec<u32>> {
let rows = chain.last().map_or(0, Vec::len);
let mut out = vec![Vec::new(); rows];
for (step, pair) in chain.windows(2).enumerate() {
let value = step as u32 + 1;
for row in 0..rows {
for _ in pair[0][row]..pair[1][row] {
out[row].push(value);
}
}
}
out
}
pub fn kostka_table(n: u32) -> Vec<Vec<u128>> {
kostka_table_in::<i128>(n)
.into_iter()
.map(|row| row.into_iter().map(|v| v as u128).collect())
.collect()
}
pub fn kostka_table_in<C: Ring>(n: u32) -> Vec<Vec<C>> {
let parts = crate::memo::partitions_cached(n);
let mut table = vec![vec![C::zero(); parts.len()]; parts.len()];
if n == 0 {
table[0][0] = C::one();
return table;
}
let l = n as usize;
if l <= MASK_LIMIT {
let index: Map<u64, usize> = parts
.iter()
.enumerate()
.map(|(i, p)| (beta_mask(p, l), i))
.collect();
let leaves: Vec<(&Partition, usize)> = parts.iter().zip(0..).collect();
pieri_trie(
&leaves,
0,
&unit_mask_layer(l),
false,
&mut |_, &col, layer| {
crate::interrupt::poll();
for (mask, &v) in layer {
table[index[mask]][col] = C::from_i128(v);
}
},
);
return table;
}
table_on_partitions(n, &parts, table)
}
fn table_on_partitions<C: Ring>(
n: u32,
parts: &[Partition],
mut table: Vec<Vec<C>>,
) -> Vec<Vec<C>> {
let index: HashMap<&[u32], usize> = parts
.iter()
.enumerate()
.map(|(i, p)| (p.parts(), i))
.collect();
let mut order: Vec<usize> = (0..parts.len()).collect();
order.sort_by(|&a, &b| parts[a].parts().cmp(parts[b].parts()));
let mut root: HashMap<Vec<u32>, C> = HashMap::new();
root.insert(Vec::new(), C::one());
table_sweep(n, parts, &order, 0, &root, &index, &mut table);
table
}
fn table_sweep<C: Ring>(
n: u32,
parts: &[Partition],
group: &[usize],
depth: usize,
layer: &HashMap<Vec<u32>, C>,
index: &HashMap<&[u32], usize>,
table: &mut [Vec<C>],
) {
let mut i = 0;
while i < group.len() && parts[group[i]].len() == depth {
crate::interrupt::poll();
let col = group[i];
for (shape, ways) in layer {
if let Some(&row) = index.get(shape.as_slice()) {
table[row][col] = ways.clone();
}
}
i += 1;
}
while i < group.len() {
crate::interrupt::poll();
let r = parts[group[i]].part(depth);
let start = i;
while i < group.len() && parts[group[i]].part(depth) == r {
i += 1;
}
let bound = vec![n; depth + 1];
let mut next: HashMap<Vec<u32>, C> = HashMap::new();
let mut buf: Vec<u32> = Vec::new();
for (shape, ways) in layer {
buf.clear();
buf.extend_from_slice(shape);
buf.resize(bound.len(), 0);
grow(0, r, u32::MAX, &mut buf, &bound, &mut |grown: &[u32]| {
let end = grown.iter().rposition(|&x| x > 0).map_or(0, |i| i + 1);
next.entry(grown[..end].to_vec())
.or_insert_with(C::zero)
.add_assign(ways);
});
}
table_sweep(n, parts, &group[start..i], depth + 1, &next, index, table);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn swept_table_matches_per_pair_kostka() {
for n in 0..=12u32 {
let parts = crate::memo::partitions_cached(n);
let table = kostka_table(n);
assert_eq!(table.len(), parts.len(), "table is p({n}) square");
for (i, lambda) in parts.iter().enumerate() {
for (j, mu) in parts.iter().enumerate() {
assert_eq!(
table[i][j],
kostka(lambda, mu),
"K_{{{lambda},{mu}}} at degree {n}"
);
}
}
}
}
#[test]
fn small_kostka_values() {
assert_eq!(kostka(&p(&[2]), &p(&[2])), 1);
assert_eq!(kostka(&p(&[2]), &p(&[1, 1])), 1); assert_eq!(kostka(&p(&[1, 1]), &p(&[2])), 0); assert_eq!(kostka(&p(&[1, 1]), &p(&[1, 1])), 1);
assert_eq!(kostka(&p(&[2, 1]), &p(&[1, 1, 1])), 2); assert_eq!(kostka(&p(&[3, 2, 1]), &p(&[1, 1, 1, 1, 1, 1])), 16); }
#[test]
fn value_range_extends_past_the_u8_boundary() {
for len in [200usize, 255, 256, 300] {
let tall = Partition::new(std::iter::repeat_n(1, len));
assert_eq!(kostka(&tall, &tall), 1, "K_{{1^{len},1^{len}}}");
}
}
#[test]
fn standard_tableaux_count_matches_the_hook_formula() {
for parts in [
&[3u32, 2, 1][..],
&[4, 3, 2, 1],
&[5, 4, 3, 2, 1],
&[6, 5, 4, 3, 2],
&[7, 6, 5, 4, 3],
] {
let lam = p(parts);
let n = lam.size();
let ones = Partition::new(std::iter::repeat_n(1, n as usize));
let conj = lam.conjugate();
let mut hooks: u128 = 1;
for (i, &row) in lam.parts().iter().enumerate() {
for j in 0..row as usize {
hooks *= (row as u128 - j as u128) + (conj.part(j) as u128 - i as u128) - 1;
}
}
let factorial: u128 = (1..=u128::from(n)).product();
assert_eq!(
factorial % hooks,
0,
"hook product must divide n! for {lam}"
);
assert_eq!(kostka(&lam, &ones), factorial / hooks, "K_{{{lam},1^{n}}}");
}
}
#[test]
fn partition_keyed_table_matches_the_mask_route() {
for n in 1..=11u32 {
let parts = crate::memo::partitions_cached(n);
let blank = vec![vec![0i128; parts.len()]; parts.len()];
let via_parts = table_on_partitions(n, &parts, blank);
let via_masks: Vec<Vec<i128>> = kostka_table_in(n);
assert_eq!(via_parts, via_masks, "Kostka table at degree {n}");
}
}
#[test]
fn generic_table_agrees_and_accepts_a_polynomial_ring() {
use crate::qt::QtPoly;
for n in 0..=9u32 {
let plain = kostka_table(n);
let wide: Vec<Vec<i128>> = kostka_table_in(n);
let poly: Vec<Vec<QtPoly<i64>>> = kostka_table_in(n);
for i in 0..plain.len() {
for j in 0..plain.len() {
assert_eq!(plain[i][j], wide[i][j] as u128, "i128 at ({i},{j}) deg {n}");
assert_eq!(
poly[i][j].coeff(0, 0),
plain[i][j] as i64,
"QtPoly at ({i},{j}) deg {n}"
);
assert!(poly[i][j].len() <= 1);
}
}
}
}
#[test]
fn tableau_count_matches_the_kostka_number() {
for n in 0..=8u32 {
for lambda in crate::memo::partitions_cached(n).iter() {
for mu in crate::memo::partitions_cached(n).iter() {
let ts = semistandard_tableaux(lambda, mu.parts());
assert_eq!(
ts.len() as u128,
kostka(lambda, mu),
"#SSYT({lambda}, {mu})"
);
}
}
}
}
#[test]
fn every_tableau_is_semistandard_of_the_given_shape_and_weight() {
for n in 0..=7u32 {
for lambda in crate::memo::partitions_cached(n).iter() {
for mu in crate::memo::partitions_cached(n).iter() {
let ts = semistandard_tableaux(lambda, mu.parts());
let mut seen = std::collections::HashSet::new();
for t in &ts {
assert!(seen.insert(t.clone()), "{t:?} twice for {lambda}, {mu}");
let shape: Vec<u32> = t.iter().map(|r| r.len() as u32).collect();
assert_eq!(shape, lambda.parts(), "shape of {t:?}");
let mut weight = vec![0u32; mu.len()];
for row in t {
for &v in row {
weight[v as usize - 1] += 1;
}
}
assert_eq!(weight, mu.parts(), "weight of {t:?}");
for row in t {
assert!(row.windows(2).all(|w| w[0] <= w[1]), "row of {t:?}");
}
for (i, row) in t.iter().enumerate().skip(1) {
for (j, &v) in row.iter().enumerate() {
assert!(t[i - 1][j] < v, "column {j} of {t:?}");
}
}
}
}
}
}
}
#[test]
fn tableau_order_matches_symmetricas() {
assert_eq!(
semistandard_tableaux(&p(&[3, 1]), &[2, 1, 1]),
vec![vec![vec![1, 1, 2], vec![3]], vec![vec![1, 1, 3], vec![2]]]
);
assert_eq!(
semistandard_tableaux(&p(&[3, 2, 1]), &[2, 2, 2]),
vec![
vec![vec![1, 1, 2], vec![2, 3], vec![3]],
vec![vec![1, 1, 3], vec![2, 2], vec![3]],
]
);
assert_eq!(
semistandard_tableaux(&p(&[2, 2]), &[2, 1, 1]),
vec![vec![vec![1, 1], vec![2, 3]]]
);
assert_eq!(
semistandard_tableaux(&p(&[2, 2, 2]), &[2, 2, 1, 1]),
vec![vec![vec![1, 1], vec![2, 2], vec![3, 4]]]
);
}
#[test]
fn empty_shape_gives_one_tableau_and_mismatched_sizes_give_none() {
assert_eq!(
semistandard_tableaux(&p(&[]), &[]),
vec![Vec::<Vec<u32>>::new()]
);
assert!(semistandard_tableaux(&p(&[2]), &[1, 1, 1]).is_empty());
assert!(semistandard_tableaux(&p(&[1, 1]), &[2]).is_empty());
}
#[test]
fn diagonal_is_one() {
for parts in [&[2, 1][..], &[3, 1], &[2, 2], &[4]] {
let lam = p(parts);
assert_eq!(kostka(&lam, &lam), 1, "K_{{{lam},{lam}}}");
}
}
}