use std::collections::HashMap;
use std::sync::Arc;
use crate::lr::LrBackend;
use crate::memo::product_cached;
use crate::partition::Partition;
#[derive(Clone, Copy, Debug, Default)]
pub struct StripLr;
fn horizontal_strips(lambda: &[u32], r: u32) -> Vec<(Vec<u32>, Vec<u32>)> {
let rows = lambda.len() + 1; let mut out = Vec::new();
let mut cur = vec![0u32; rows];
fn rec(
j: usize,
rows: usize,
left: u32,
lambda: &[u32],
cur: &mut Vec<u32>,
out: &mut Vec<(Vec<u32>, Vec<u32>)>,
) {
if j == rows {
if left == 0 {
let mut parts: Vec<u32> = cur.iter().copied().filter(|&x| x > 0).collect();
let theta: Vec<u32> = (0..rows)
.map(|k| cur[k] - lambda.get(k).copied().unwrap_or(0))
.collect();
parts.truncate(cur.iter().filter(|&&x| x > 0).count());
out.push((parts, theta));
}
return;
}
let lam_j = lambda.get(j).copied().unwrap_or(0);
let upper = if j == 0 {
lam_j + left
} else {
let prev_old = lambda.get(j - 1).copied().unwrap_or(0);
prev_old.min(lam_j + left)
};
for v in lam_j..=upper {
let added = v - lam_j;
if added > left {
break;
}
cur[j] = v;
rec(j + 1, rows, left - added, lambda, cur, out);
}
cur[j] = 0;
}
rec(0, rows, r, lambda, &mut cur, &mut out);
out
}
fn lattice_ok(theta: &[u32], prev: &[u32]) -> bool {
let n = theta.len().max(prev.len());
let mut run_theta = 0u32;
let mut run_prev = 0u32;
for j in 0..n {
run_theta += theta.get(j).copied().unwrap_or(0);
if run_theta > run_prev {
return false;
}
run_prev += prev.get(j).copied().unwrap_or(0);
}
true
}
impl StripLr {
pub fn product(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
(*self.product_shared(mu, nu)).clone()
}
pub fn product_shared(&self, mu: &Partition, nu: &Partition) -> Arc<Vec<(Partition, u128)>> {
product_cached(mu, nu, || self.product_uncached(mu, nu))
}
fn product_uncached(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
let mut states: HashMap<(Vec<u32>, Vec<u32>), u128> = HashMap::new();
states.insert((mu.parts().to_vec(), Vec::new()), 1);
for (i, &r) in nu.parts().iter().enumerate() {
let mut next: HashMap<(Vec<u32>, Vec<u32>), u128> = HashMap::new();
for ((cur, prev), mult) in &states {
for (grown, theta) in horizontal_strips(cur, r) {
if i > 0 && !lattice_ok(&theta, prev) {
continue;
}
*next.entry((grown, theta)).or_insert(0) += mult;
}
}
states = next;
}
let mut totals: HashMap<Vec<u32>, u128> = HashMap::new();
for ((shape, _), mult) in states {
*totals.entry(shape).or_insert(0) += mult;
}
let mut out: Vec<(Partition, u128)> = totals
.into_iter()
.map(|(parts, c)| (Partition::from_sorted(parts), c))
.collect();
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
}
impl LrBackend for StripLr {
fn lr_coeff(&self, lambda: &Partition, mu: &Partition, nu: &Partition) -> u128 {
if lambda.size() != mu.size() + nu.size() || !lambda.contains(mu) {
return 0;
}
self.product_shared(mu, nu)
.iter()
.find(|(l, _)| l == lambda)
.map(|(_, c)| *c)
.unwrap_or(0)
}
fn schur_product(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
self.product(mu, nu)
}
fn schur_product_shared(&self, mu: &Partition, nu: &Partition) -> Arc<Vec<(Partition, u128)>> {
self.product_shared(mu, nu)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::lr::NaiveLr;
use crate::partition::partitions_of;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn known_products() {
let got = StripLr.product(&p(&[1]), &p(&[1]));
let shapes: Vec<(Vec<u32>, u128)> =
got.iter().map(|(l, c)| (l.parts().to_vec(), *c)).collect();
assert_eq!(shapes, vec![(vec![1, 1], 1), (vec![2], 1)]);
assert_eq!(
StripLr.lr_coeff(&p(&[3, 2, 1]), &p(&[2, 1]), &p(&[2, 1])),
2
);
}
#[test]
fn agrees_with_naive_backend_exhaustively() {
let mut checked = 0;
for a in 0..=7u32 {
for b in 0..=(7 - a) {
for mu in partitions_of(a) {
for nu in partitions_of(b) {
let fast = StripLr.schur_product(&mu, &nu);
let slow = NaiveLr.schur_product(&mu, &nu);
assert_eq!(fast, slow, "s{mu}*s{nu}");
checked += 1;
}
}
}
}
assert!(checked > 200, "expected a real sweep, got {checked}");
}
#[test]
fn schur_product_shared_agrees_with_schur_product_on_every_backend() {
use crate::skew_lr::SkewLr;
for a in 0..=5u32 {
for b in 0..=(5 - a) {
for mu in partitions_of(a) {
for nu in partitions_of(b) {
let want = NaiveLr.schur_product(&mu, &nu);
assert_eq!(
*NaiveLr.schur_product_shared(&mu, &nu),
want,
"Naive s{mu}*s{nu}"
);
assert_eq!(
*StripLr.schur_product_shared(&mu, &nu),
want,
"Strip s{mu}*s{nu}"
);
assert_eq!(
*SkewLr.schur_product_shared(&mu, &nu),
want,
"Skew s{mu}*s{nu}"
);
assert_eq!(
*AutoLr.schur_product_shared(&mu, &nu),
want,
"Auto s{mu}*s{nu}"
);
}
}
}
}
}
#[test]
fn every_route_of_auto_lr_is_memoized_under_one_entry() {
use crate::skew_lr::SkewLr;
let rect = (p(&[3, 3, 3]), p(&[2, 2]));
let two = (p(&[15, 13, 11]), p(&[19, 17]));
let three = (p(&[10, 8, 6]), p(&[9, 8, 7]));
let general = (p(&[5, 3, 2, 1]), p(&[4, 2, 1]));
assert!(crate::rect::okada_product(&rect.0, &rect.1).is_some());
assert!(crate::two_row::prefer_counting(&two.0, &two.1));
assert!(crate::two_row::two_row_product(&two.0, &two.1).is_some());
assert!(crate::three_row::prefer_counting(&three.0, &three.1));
assert!(crate::three_row::three_row_product(&three.0, &three.1).is_some());
assert!(!crate::two_row::prefer_counting(&general.0, &general.1));
assert!(!crate::three_row::prefer_counting(&general.0, &general.1));
for (mu, nu) in [rect, two, three, general] {
let first = AutoLr.schur_product_shared(&mu, &nu);
let again = AutoLr.schur_product_shared(&mu, &nu);
assert!(Arc::ptr_eq(&first, &again), "s{mu}·s{nu} recomputed");
let swapped = AutoLr.schur_product_shared(&nu, &mu);
assert!(Arc::ptr_eq(&first, &swapped), "s{nu}·s{mu} stored apart");
let layer = SkewLr.schur_product_shared(&mu, &nu);
assert!(
Arc::ptr_eq(&first, &layer),
"SkewLr keeps s{mu}·s{nu} apart"
);
let n = mu.size() + nu.size();
let sweep: Vec<Partition> = if n <= 20 {
partitions_of(n)
} else {
let mut v: Vec<Partition> = first.iter().map(|(l, _)| l.clone()).collect();
let mut tall = mu.parts().to_vec();
tall[0] += nu.part(0);
tall.extend(std::iter::repeat_n(1, (nu.size() - nu.part(0)) as usize));
v.push(Partition::new(tall));
let mut wide = mu.parts().to_vec();
wide[0] += nu.size();
v.push(Partition::new(wide));
v
};
let mut seen = 0;
for lambda in &sweep {
let want = first
.binary_search_by(|(l, _)| l.cmp(lambda))
.map_or(0, |i| first[i].1);
assert_eq!(
AutoLr.lr_coeff(lambda, &mu, &nu),
want,
"c^{lambda}_{{{mu},{nu}}}"
);
seen += usize::from(want != 0);
}
assert_eq!(seen, first.len(), "s{mu}·s{nu}: the sweep missed terms");
assert!(seen < sweep.len(), "s{mu}·s{nu}: no zero was asked for");
}
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct AutoLr;
pub const STRIP_THRESHOLD: u32 = 36;
impl LrBackend for AutoLr {
fn lr_coeff(&self, lambda: &Partition, mu: &Partition, nu: &Partition) -> u128 {
if let Some(c) = crate::rect::okada_coeff(lambda, mu, nu) {
return c;
}
crate::skew_lr::SkewLr.lr_coeff(lambda, mu, nu)
}
fn schur_product(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
(*self.schur_product_shared(mu, nu)).clone()
}
fn schur_product_shared(&self, mu: &Partition, nu: &Partition) -> Arc<Vec<(Partition, u128)>> {
crate::skew_lr::memoized_product(mu, nu, || {
if let Some(v) = crate::rect::okada_product(mu, nu) {
return Some(v);
}
if crate::two_row::prefer_counting(mu, nu) {
if let Some(v) = crate::two_row::two_row_product(mu, nu) {
return Some(v);
}
}
if crate::three_row::prefer_counting(mu, nu) {
if let Some(v) = crate::three_row::three_row_product(mu, nu) {
return Some(v);
}
}
None
})
}
}