#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::sync::Arc;
use crate::memo::{lr_cached, partitions_cached};
use crate::partition::Partition;
pub trait LrBackend {
fn lr_coeff(&self, lambda: &Partition, mu: &Partition, nu: &Partition) -> u128;
fn schur_product(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
let n = mu.size() + nu.size();
let mut out = Vec::new();
for lambda in partitions_cached(n).iter() {
if lambda.len() > mu.len() + nu.len()
|| lambda.part(0) > mu.part(0) + nu.part(0)
|| !lambda.contains(mu)
{
continue;
}
let c = self.lr_coeff(lambda, mu, nu);
if c != 0 {
out.push((lambda.clone(), c));
}
}
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
fn schur_product_shared(&self, mu: &Partition, nu: &Partition) -> Arc<Vec<(Partition, u128)>> {
Arc::new(self.schur_product(mu, nu))
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct NaiveLr;
impl LrBackend for NaiveLr {
fn lr_coeff(&self, lambda: &Partition, mu: &Partition, nu: &Partition) -> u128 {
if lambda.size() != mu.size() + nu.size() || !lambda.contains(mu) || !lambda.contains(nu) {
return 0;
}
let (inner, content) = if mu.size() >= nu.size() {
(mu, nu)
} else {
(nu, mu)
};
lr_cached(lambda, inner, content, || {
lr_coeff_uncached(lambda, inner, content)
})
}
}
fn lr_coeff_uncached(lambda: &Partition, mu: &Partition, nu: &Partition) -> u128 {
{
let maxval = nu.len();
if maxval == 0 {
return if lambda == mu { 1 } else { 0 };
}
let rows = lambda.len();
let width = lambda.part(0) as usize;
let mut grid = vec![vec![0u32; width]; rows];
let mut cells = Vec::new();
for r in 0..rows {
let start = mu.part(r) as usize;
let end = lambda.part(r) as usize;
for c in (start..end).rev() {
cells.push((r, c));
}
}
let cap: Vec<u32> = nu.parts().to_vec();
let mut used = vec![0u32; maxval]; let mut cnt = vec![0i64; maxval + 2]; let mut count: u128 = 0;
let mut st = State {
cells: &cells,
grid: &mut grid,
lambda,
mu,
maxval,
cap: &cap,
used: &mut used,
cnt: &mut cnt,
count: &mut count,
};
backtrack(0, &mut st);
count
}
}
struct State<'a> {
cells: &'a [(usize, usize)],
grid: &'a mut [Vec<u32>],
lambda: &'a Partition,
mu: &'a Partition,
maxval: usize,
cap: &'a [u32],
used: &'a mut [u32],
cnt: &'a mut [i64],
count: &'a mut u128,
}
fn backtrack(idx: usize, st: &mut State) {
if idx == st.cells.len() {
*st.count += 1;
return;
}
let (r, c) = st.cells[idx];
let end_r = st.lambda.part(r) as usize;
let right = if c + 1 < end_r {
st.grid[r][c + 1]
} else {
st.maxval as u32
};
let top = if r > 0 && c >= st.mu.part(r - 1) as usize && c < st.lambda.part(r - 1) as usize {
st.grid[r - 1][c]
} else {
0
};
for v in 1..=st.maxval as u32 {
let vi = (v - 1) as usize;
if st.used[vi] >= st.cap[vi] {
continue; }
if v > right {
continue; }
if v <= top {
continue; }
if v >= 2 && st.cnt[v as usize] + 1 > st.cnt[(v - 1) as usize] {
continue;
}
st.grid[r][c] = v;
st.used[vi] += 1;
st.cnt[v as usize] += 1;
backtrack(idx + 1, st);
st.cnt[v as usize] -= 1;
st.used[vi] -= 1;
st.grid[r][c] = 0;
}
}
#[cfg(test)]
mod tests {
use super::*;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn pieri_s1_s1() {
let prod = NaiveLr.schur_product(&p(&[1]), &p(&[1]));
let mut got: Vec<_> = prod.iter().map(|(l, c)| (l.parts().to_vec(), *c)).collect();
got.sort();
assert_eq!(got, vec![(vec![1, 1], 1), (vec![2], 1)]);
}
#[test]
fn value_range_extends_past_the_u8_boundary() {
let empty = Partition::default();
for len in [255usize, 256, 300] {
let tall = Partition::new(std::iter::repeat_n(1, len));
assert_eq!(
NaiveLr.lr_coeff(&tall, &empty, &tall),
1,
"c^(1^{len})_(∅,1^{len}) with ℓ(ν) = {len}"
);
}
}
#[test]
fn s21_squared_has_multiplicity_two() {
let coeff = NaiveLr.lr_coeff(&p(&[3, 2, 1]), &p(&[2, 1]), &p(&[2, 1]));
assert_eq!(coeff, 2, "c^{{321}}_{{21,21}} should be 2");
let prod = NaiveLr.schur_product(&p(&[2, 1]), &p(&[2, 1]));
let total: u128 = prod.iter().map(|(_, c)| *c).sum();
assert_eq!(total, 8, "sum of LR coeffs = f^{{21}} squared count");
assert!(prod.iter().all(|(l, _)| l.size() == 6));
}
}