#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::partition::Partition;
fn orient<'a>(a: &'a Partition, b: &'a Partition) -> Option<(&'a Partition, &'a Partition)> {
match (a.len() == 3, b.len() == 3) {
(true, true) => Some(if (a.size(), a.parts()) <= (b.size(), b.parts()) {
(b, a)
} else {
(a, b)
}),
(false, true) => Some((a, b)),
(true, false) => Some((b, a)),
(false, false) => None,
}
}
pub fn prefer_counting(a: &Partition, b: &Partition) -> bool {
let Some((mu, nu)) = orient(a, b) else {
return false;
};
let rows = mu.len();
let (n1, n3) = (nu.part(0), nu.part(2));
let (m, v) = (mu.size(), nu.size());
rows >= 3 && 3 * n3 >= n1 && 8 * v >= m && 3 * m >= v && m + v >= 48
}
pub fn three_row_product(a: &Partition, b: &Partition) -> Option<Vec<(Partition, u128)>> {
let (mu_p, nu_p) = orient(a, b)?;
let mu: Vec<u32> = mu_p.parts().to_vec();
let nu: Vec<u32> = nu_p.parts().to_vec();
let max_l1 = (mu_p.part(0) + nu_p.size()) as usize;
if nu[0] > 1023 || max_l1 > 4095 {
return None;
}
let threads = std::thread::available_parallelism().map_or(1, |n| n.get());
Some(crate::candidates::count_all(
&mu,
3,
nu_p.size(),
threads,
|| {
let mut st = Fiber::new(&mu, &nu, max_l1);
move |lam: &[u32]| st.count(lam)
},
))
}
struct Table {
gen: Vec<u32>,
val: Vec<u128>,
touched: Vec<u32>,
era: u32,
stride_a: usize,
stride_l: usize,
}
impl Table {
fn new(max_l1: usize, n1: usize, n2: usize) -> Table {
let stride_a = n2 + 1;
let stride_l = (n1 + 1) * stride_a;
let size = (max_l1 + 1) * stride_l;
Table {
gen: vec![0; size],
val: vec![0; size],
touched: Vec::with_capacity(256),
era: 0,
stride_a,
stride_l,
}
}
fn clear(&mut self) {
self.era += 1;
self.touched.clear();
}
#[inline]
fn add(&mut self, l1: usize, a: usize, b: usize, ways: u128) {
let i = l1 * self.stride_l + a * self.stride_a + b;
if self.gen[i] != self.era {
self.gen[i] = self.era;
self.val[i] = 0;
self.touched.push(((l1 << 20) | (a << 10) | b) as u32);
}
self.val[i] += ways;
}
#[inline]
fn get(&self, l1: usize, a: usize, b: usize) -> u128 {
self.val[l1 * self.stride_l + a * self.stride_a + b]
}
}
#[inline]
fn unpack(t: u32) -> (i64, i64, i64) {
(
i64::from(t >> 20),
i64::from((t >> 10) & 0x3ff),
i64::from(t & 0x3ff),
)
}
struct Fiber<'a> {
mu: &'a [u32],
nu: &'a [u32],
cur: Table,
nxt: Table,
}
impl<'a> Fiber<'a> {
fn new(mu: &'a [u32], nu: &'a [u32], max_l1: usize) -> Fiber<'a> {
Fiber {
mu,
nu,
cur: Table::new(max_l1, nu[0] as usize, nu[1] as usize),
nxt: Table::new(max_l1, nu[0] as usize, nu[1] as usize),
}
}
}
fn at(v: &[u32], i: usize) -> i64 {
v.get(i).copied().map_or(0, i64::from)
}
impl Fiber<'_> {
fn count(&mut self, lam: &[u32]) -> u128 {
let (n1, n2) = (at(self.nu, 0), at(self.nu, 1));
self.cur.clear();
self.cur.add(at(lam, 0) as usize, 0, 0, 1);
let (mut big_lam, mut big_mu) = (0i64, 0i64);
for j in 0..lam.len() {
big_lam += at(lam, j);
big_mu += at(self.mu, j);
let mu_j = at(self.mu, j);
let l1_lo = mu_j.max(at(lam, j + 2));
let l1_hi = if j == 0 {
at(lam, 0)
} else {
at(self.mu, j - 1).min(at(lam, j))
};
let (lam_j, lam_j1) = (at(lam, j), at(lam, j + 1));
let d = big_lam - big_mu;
self.nxt.clear();
let (cur, nxt) = (&self.cur, &mut self.nxt);
for &t in &cur.touched {
let (l1_prev, a_prev, b_prev) = unpack(t);
let ways = cur.get(l1_prev as usize, a_prev as usize, b_prev as usize);
let l2_hi = l1_prev.min(lam_j);
if l2_hi < lam_j1 {
continue; }
let l1_top = l1_hi.min(mu_j + n1 - a_prev).min(l2_hi);
for l1 in l1_lo..=l1_top {
let a = a_prev + l1 - mu_j;
let b_lo = (b_prev + l1.max(lam_j1) - l1).max(d - a - b_prev);
let b_hi = (b_prev + l2_hi - l1).min(n2).min(a_prev).min(d - a);
for b in b_lo..=b_hi {
nxt.add(l1 as usize, a as usize, b as usize, ways);
}
}
}
std::mem::swap(&mut self.cur, &mut self.nxt);
if self.cur.touched.is_empty() {
return 0;
}
}
let mut total = 0u128;
for &t in &self.cur.touched {
let (l1, a, b) = unpack(t);
if a == n1 && b == n2 {
total += self.cur.get(l1 as usize, a as usize, b as usize);
}
}
total
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::lr::LrBackend;
use crate::skew_lr::SkewLr;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn agrees_with_skew_lr_on_three_row_factors() {
let mut cases = 0;
for n1 in 1..=4u32 {
for n2 in 1..=n1 {
for n3 in 1..=n2 {
let nu = p(&[n1, n2, n3]);
for mu_parts in [
&[1u32][..],
&[3],
&[2, 1],
&[3, 2],
&[2, 2, 1],
&[4, 2, 1],
&[3, 3, 3],
&[4, 3, 2, 1],
&[5, 3, 2, 1],
] {
let mu = p(mu_parts);
assert_eq!(
three_row_product(&mu, &nu).as_ref(),
Some(&SkewLr.schur_product(&mu, &nu)),
"s{mu} · s{nu}"
);
assert_eq!(
three_row_product(&nu, &mu).as_ref(),
Some(&SkewLr.schur_product(&nu, &mu)),
"s{nu} · s{mu} (swapped)"
);
cases += 1;
}
}
}
}
assert!(cases >= 100, "expected a real sweep, got {cases}");
}
#[test]
fn two_three_row_factors_are_orientation_independent() {
let shapes = [
p(&[1, 1, 1]),
p(&[3, 2, 1]),
p(&[4, 4, 2]),
p(&[5, 3, 1]),
p(&[2, 2, 2]),
];
for x in &shapes {
for y in &shapes {
let want = SkewLr.schur_product(x, y);
assert_eq!(three_row_product(x, y).as_ref(), Some(&want), "s{x}·s{y}");
assert_eq!(
three_row_product(y, x).as_ref(),
Some(&SkewLr.schur_product(y, x)),
"s{y}·s{x} (swapped)"
);
assert_eq!(
prefer_counting(x, y),
prefer_counting(y, x),
"dispatch must not depend on argument order: s{x}·s{y}"
);
}
}
}
#[test]
fn degenerate_factors() {
let nu = p(&[3, 2, 1]);
assert_eq!(
three_row_product(&Partition::default(), &nu),
Some(vec![(nu.clone(), 1)])
);
for mu in [p(&[1]), p(&[5]), p(&[9])] {
assert_eq!(
three_row_product(&mu, &nu).as_ref(),
Some(&SkewLr.schur_product(&mu, &nu)),
"s{mu} · s{nu}"
);
}
}
#[test]
fn declines_without_a_three_row_factor() {
for (a, b) in [
(p(&[3, 2, 1, 1]), p(&[2, 1])),
(p(&[4]), p(&[3])),
(p(&[2, 2]), p(&[1])),
(Partition::default(), Partition::default()),
] {
assert_eq!(three_row_product(&a, &b), None, "s{a} · s{b}");
}
}
#[test]
fn declines_shapes_wider_than_the_packed_state() {
assert_eq!(three_row_product(&p(&[5, 4]), &p(&[1030, 2, 1])), None);
assert_eq!(three_row_product(&p(&[4090, 8, 4]), &p(&[8, 6, 4])), None);
assert!(three_row_product(&p(&[4070, 8, 4]), &p(&[8, 6, 4])).is_some());
}
#[test]
fn multiplicities_match() {
let (mu, nu) = (p(&[5, 4, 3]), p(&[4, 3, 2]));
let got = three_row_product(&mu, &nu).expect("three-row");
assert_eq!(got, SkewLr.schur_product(&mu, &nu));
assert!(
got.iter().any(|(_, c)| *c >= 5),
"expected a coefficient ≥ 5 to make this test meaningful"
);
}
#[test]
fn dispatched_path_agrees_with_the_engine() {
let mu = p(&[20, 16, 12]);
assert!(prefer_counting(&mu, &mu), "shape must actually dispatch");
assert_eq!(
crate::strip_lr::AutoLr.schur_product(&mu, &mu),
SkewLr.schur_product(&mu, &mu)
);
}
#[test]
fn dispatch_predicate_matches_the_calibration() {
let cases: &[(&[u32], &[u32], bool)] = &[
(&[20, 16, 12], &[20, 16, 12], true), (&[24, 20, 16], &[24, 20, 16], true), (&[22, 18, 14], &[22, 18, 14], true), (&[14, 12, 10], &[14, 12, 10], true), (&[12, 10, 8], &[12, 10, 8], true), (&[10, 8, 6], &[10, 8, 6], true), (&[16, 13, 10, 7], &[8, 6, 4], true), (&[14, 12, 10, 8, 6], &[7, 5, 3], true), (&[12, 11, 10, 9, 8, 7], &[6, 5, 4], true), (&[16, 14, 12, 10, 8, 6, 4], &[10, 8, 6], true), (&[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], &[9, 7, 5], true), (&[14, 13, 12, 11, 10, 9, 8, 7, 6, 5], &[6, 5, 4], true), (&[8, 6, 4], &[8, 6, 4], false), (&[30, 24, 18], &[40, 2, 1], false), (&[30, 24, 18], &[3, 2, 1], false), ];
for (m, n, want) in cases {
let (mu, nu) = (p(m), p(n));
assert_eq!(prefer_counting(&mu, &nu), *want, "s{mu} · s{nu}");
assert_eq!(prefer_counting(&nu, &mu), *want, "s{nu} · s{mu}");
}
}
}