#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::coeff::Ring;
use crate::partition::Partition;
use crate::qt::QtPoly;
pub fn charge(word: &[u32]) -> u32 {
let Some(&top) = word.iter().max() else {
return 0;
};
let mut counts = vec![0u32; top as usize + 1];
for &c in word {
counts[c as usize] += 1;
}
if counts[1..].iter().all(|&c| c <= 1) {
return standard_charge(word);
}
let mut rest: Vec<Option<u32>> = word.iter().map(|&c| Some(c)).collect();
let mut total = 0;
while rest.iter().any(|c| c.is_some()) {
let sub = peel_standard(&mut rest);
if sub.is_empty() {
break; }
total += standard_charge(&sub);
}
total
}
fn standard_charge(word: &[u32]) -> u32 {
let top = match word.iter().max() {
Some(&m) => m as usize,
None => return 0,
};
let mut at = vec![usize::MAX; top + 1];
for (j, &c) in word.iter().enumerate() {
at[c as usize] = j;
}
let mut index = 0u32;
let mut total = 0u32;
let mut prev = usize::MAX;
for c in 1..=top {
let pos = at[c];
if pos == usize::MAX {
continue;
}
if prev != usize::MAX && pos > prev {
index += 1;
}
total += index;
prev = pos;
}
total
}
fn peel_standard(rest: &mut [Option<u32>]) -> Vec<u32> {
let n = rest.len();
let mut picked: Vec<(usize, u32)> = Vec::new();
let mut target = 1u32;
let mut from = n; loop {
let mut found = None;
for step in 0..n {
let j = (from + n - 1 - step) % n;
if rest[j] == Some(target) {
found = Some(j);
break;
}
}
match found {
Some(j) => {
rest[j] = None;
picked.push((j, target));
target += 1;
from = j;
}
None => break,
}
}
picked.sort_unstable_by_key(|&(j, _)| j);
picked.into_iter().map(|(_, c)| c).collect()
}
pub fn kostka_foulkes_by_charge<C: Ring>(lambda: &Partition, mu: &Partition) -> QtPoly<C> {
let mut out = QtPoly::zero();
if lambda.size() != mu.size() {
return out;
}
if lambda.is_empty() {
return <QtPoly<C> as Ring>::one();
}
let rows = lambda.len();
let mut chain: Vec<Vec<u32>> = vec![vec![0; rows]];
let target: Vec<u32> = lambda.parts().to_vec();
build(&target, mu.parts(), 0, &mut chain, &mut |ch| {
let w = reading_word(&target, ch);
out.add_term(0, charge(&w), C::one());
});
out
}
pub(crate) fn build(
target: &[u32],
mu: &[u32],
k: usize,
chain: &mut Vec<Vec<u32>>,
emit: &mut impl FnMut(&[Vec<u32>]),
) {
if k == mu.len() {
if chain
.last()
.expect("the chain starts at the empty shape")
.as_slice()
== target
{
emit(chain);
}
return;
}
let cur = chain
.last()
.expect("the chain starts at the empty shape")
.clone();
let mut next = cur.clone();
strips(target, &cur, 0, u32::MAX, mu[k], &mut next, &mut |shape| {
chain.push(shape.to_vec());
build(target, mu, k + 1, chain, emit);
chain.pop();
});
}
pub(crate) fn strips(
target: &[u32],
cur: &[u32],
i: usize,
prev: u32,
left: u32,
out: &mut Vec<u32>,
emit: &mut impl FnMut(&[u32]),
) {
if i == target.len() {
if left == 0 {
emit(out);
}
return;
}
let hi = prev.min(target[i]).min(cur[i] + left);
for v in cur[i]..=hi {
out[i] = v;
strips(target, cur, i + 1, cur[i], left - (v - cur[i]), out, emit);
}
out[i] = cur[i];
}
fn reading_word(target: &[u32], chain: &[Vec<u32>]) -> Vec<u32> {
let mut word = Vec::new();
for i in (0..target.len()).rev() {
for j in 0..target[i] as usize {
let letter = (1..chain.len())
.find(|&k| chain[k][i] as usize > j)
.unwrap_or(chain.len() - 1);
word.push(letter as u32);
}
}
word
}
#[cfg(test)]
mod tests {
use super::*;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn charge_on_standard_words_matches_hand_computation() {
assert_eq!(charge(&[3, 1, 2]), 2);
assert_eq!(charge(&[2, 1, 3]), 1);
assert_eq!(charge(&[3, 4, 1, 2]), 4);
assert_eq!(charge(&[2, 4, 1, 3]), 2);
assert_eq!(charge(&[1, 2, 3, 4]), 6);
assert_eq!(charge(&[4, 3, 2, 1]), 0);
}
#[test]
fn charge_of_a_repeated_word_splits_into_subwords() {
assert_eq!(charge(&[1, 1, 2]), charge(&[1, 2]) + charge(&[1]));
assert_eq!(charge(&[]), 0);
assert_eq!(charge(&[1, 1, 1]), 0);
}
#[test]
fn kostka_foulkes_specializes_to_kostka_at_one() {
for n in 0..=7u32 {
let parts = crate::partitions_of(n);
for lambda in &parts {
for mu in &parts {
let k: QtPoly<i64> = kostka_foulkes_by_charge(lambda, mu);
assert_eq!(
k.eval(&0, &1) as u128,
crate::kostka::kostka(lambda, mu),
"K_{lambda}{mu}(1) must be the Kostka number"
);
if lambda == mu {
assert_eq!(k, <QtPoly<i64> as Ring>::one(), "K_{lambda}{lambda} = 1");
}
}
}
}
}
#[test]
fn known_kostka_foulkes_values() {
let k: QtPoly<i64> = kostka_foulkes_by_charge(&part(&[2, 1]), &part(&[1, 1, 1]));
assert_eq!(k.coeff(0, 1), 1);
assert_eq!(k.coeff(0, 2), 1);
assert_eq!(k.len(), 2, "{k}");
let k: QtPoly<i64> = kostka_foulkes_by_charge(&part(&[2, 2]), &part(&[1, 1, 1, 1]));
assert_eq!(k.coeff(0, 2), 1);
assert_eq!(k.coeff(0, 4), 1);
assert_eq!(k.len(), 2, "{k}");
let k: QtPoly<i64> = kostka_foulkes_by_charge(&part(&[3, 2, 1]), &part(&[2, 2, 1, 1]));
assert_eq!(k.coeff(0, 1), 1);
assert_eq!(k.coeff(0, 2), 2);
assert_eq!(k.coeff(0, 3), 1);
assert_eq!(k.len(), 3, "{k}");
}
#[test]
fn support_matches_dominance() {
for n in 0..=7u32 {
let parts = crate::partitions_of(n);
for lambda in &parts {
for mu in &parts {
let k: QtPoly<i64> = kostka_foulkes_by_charge(lambda, mu);
let kostka = crate::kostka::kostka(lambda, mu);
assert_eq!(k.is_zero(), kostka == 0, "support at {lambda}, {mu}");
}
}
}
}
}