#![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)> {
if b.len() == 2 {
Some((a, b))
} else if a.len() == 2 {
Some((b, a))
} else {
None
}
}
pub fn applies(a: &Partition, b: &Partition) -> bool {
orient(a, b).is_some()
}
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, n2) = (nu.part(0), nu.part(1));
let (m, v) = (mu.size(), nu.size());
rows >= 2 && 4 * n2 >= n1 && 8 * v >= m && 2 * m >= v && m + v >= 75
}
pub fn two_row_coeff(lambda: &Partition, a: &Partition, b: &Partition) -> Option<u128> {
let (mu, nu) = orient(a, b)?;
if lambda.size() != mu.size() + nu.size() || !lambda.contains(mu) {
return Some(0);
}
let mu_v: Vec<u32> = mu.parts().to_vec();
Some(Fiber::new(&mu_v, nu.part(0)).count(lambda.parts()))
}
pub fn two_row_product(a: &Partition, b: &Partition) -> Option<Vec<(Partition, u128)>> {
let (mu, nu) = orient(a, b)?;
let mu: Vec<u32> = mu.parts().to_vec();
let (n1, n2) = (nu.part(0), nu.part(1));
let threads = std::thread::available_parallelism().map_or(1, |n| n.get());
Some(crate::candidates::count_all(
&mu,
2,
n1 + n2,
threads,
|| {
let mut st = Fiber::new(&mu, n1);
move |lam: &[u32]| st.count(lam)
},
))
}
struct Fiber<'a> {
mu: &'a [u32],
target: i64,
cur: Vec<u128>,
nxt: Vec<i128>,
}
impl<'a> Fiber<'a> {
fn new(mu: &'a [u32], n1: u32) -> Fiber<'a> {
let mu_size: u32 = mu.iter().sum();
let span = (mu_size + n1) as usize + 1;
Fiber {
mu,
target: i64::from(mu_size) + i64::from(n1),
cur: vec![0u128; span + 1],
nxt: vec![0i128; span + 2],
}
}
fn mu_at(&self, i: usize) -> u32 {
self.mu.get(i).copied().unwrap_or(0)
}
fn count(&mut self, lam: &[u32]) -> u128 {
let target = self.target;
let span = target as usize + 1;
self.cur[..=span].fill(0);
self.cur[0] = 1;
let (mut win_lo, mut win_hi) = (0usize, 0usize);
let (mut big_lam, mut big_mu) = (0i64, 0i64);
for (i, &lam_i) in lam.iter().enumerate() {
big_lam += i64::from(lam_i);
let lo_i =
i64::from(self.mu_at(i)).max(i64::from(lam.get(i + 1).copied().unwrap_or(0)));
let hi_i = if i == 0 {
i64::from(lam[0])
} else {
i64::from(self.mu_at(i - 1)).min(i64::from(lam_i))
};
if hi_i < lo_i {
return 0;
}
self.nxt[..=span + 1].fill(0);
let (mut new_lo, mut new_hi) = (usize::MAX, 0usize);
for l_prev in win_lo..=win_hi {
let ways = self.cur[l_prev];
if ways == 0 {
continue;
}
let need = big_lam + big_mu - 2 * l_prev as i64;
let lo = lo_i.max(need);
if lo > hi_i {
continue;
}
let s = l_prev as i64 + lo;
if s > target {
continue;
}
let e = (l_prev as i64 + hi_i).min(target);
let ways = i128::try_from(ways).unwrap_or_else(|_| {
panic!("a two-row multiplicity of {ways} does not fit i128")
});
self.nxt[s as usize] += ways;
self.nxt[e as usize + 1] -= ways;
new_lo = new_lo.min(s as usize);
new_hi = new_hi.max(e as usize);
}
if new_lo == usize::MAX {
return 0; }
let mut run: i128 = 0;
for l in 0..=new_hi {
run += self.nxt[l];
debug_assert!(run >= 0, "a tableau count went negative at {l}");
self.cur[l] = run as u128;
}
win_lo = new_lo;
win_hi = new_hi;
big_mu += i64::from(self.mu_at(i));
}
if win_lo <= target as usize && target as usize <= win_hi {
self.cur[target as usize]
} else {
0
}
}
}
#[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_two_row_factors() {
let mut cases = 0;
for n1 in 1..=5u32 {
for n2 in 1..=n1 {
let nu = p(&[n1, n2]);
for mu_parts in [
&[1u32][..],
&[2],
&[2, 1],
&[3, 1],
&[2, 2],
&[3, 2, 1],
&[4, 2, 1],
&[5, 3, 2],
&[3, 3, 3],
&[4, 4, 2, 1],
] {
let mu = p(mu_parts);
let want = SkewLr.schur_product(&mu, &nu);
assert_eq!(
two_row_product(&mu, &nu).as_ref(),
Some(&want),
"s{mu} · s{nu}"
);
assert_eq!(
two_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_row_times_two_row_is_orientation_independent() {
for a in 1..=6u32 {
for b in 1..=a {
for c in 1..=6u32 {
for d in 1..=c {
let (x, y) = (p(&[a, b]), p(&[c, d]));
let want = SkewLr.schur_product(&x, &y);
assert_eq!(two_row_product(&x, &y).as_ref(), Some(&want), "s{x}·s{y}");
assert_eq!(
two_row_product(&y, &x).as_ref(),
Some(&SkewLr.schur_product(&y, &x))
);
}
}
}
}
}
#[test]
fn degenerate_factors() {
let nu = p(&[3, 2]);
assert_eq!(
two_row_product(&Partition::default(), &nu),
Some(vec![(nu.clone(), 1)])
);
for mu in [p(&[1]), p(&[4]), p(&[7])] {
assert_eq!(
two_row_product(&mu, &nu).as_ref(),
Some(&SkewLr.schur_product(&mu, &nu)),
"s{mu} · s{nu}"
);
}
}
#[test]
fn declines_without_a_two_row_factor() {
for (a, b) in [
(p(&[3, 2, 1]), p(&[2, 1, 1])),
(p(&[4]), p(&[3])),
(p(&[2, 2, 2]), p(&[1])),
(Partition::default(), Partition::default()),
] {
assert_eq!(two_row_product(&a, &b), None, "s{a} · s{b}");
assert!(!applies(&a, &b));
}
}
#[test]
fn dispatch_predicate_matches_the_calibration() {
let cases: &[(&[u32], &[u32], bool)] = &[
(&[20, 16, 12], &[20, 16], true), (&[40, 32, 24], &[40, 32], true), (&[24, 20, 16, 12], &[24, 20], true), (&[30, 24, 18], &[30, 24], true), (&[70, 42], &[70, 42], true), (&[14, 13, 12, 11, 10, 9, 8, 7, 6, 5], &[14, 11], true), (&[20, 18, 16, 14, 12, 10, 8, 6], &[20, 16], true), (
&[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1],
&[10, 8],
true,
), (&[10, 8, 6], &[10, 8], false), (&[160], &[80, 50], false), (&[30, 24, 18], &[40, 2], false), (&[30, 24, 18], &[6, 5], true), (&[8, 6, 4], &[40, 32], 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}");
}
}
#[test]
fn dispatched_path_agrees_with_the_engine() {
let (mu, nu) = (p(&[16, 13, 10, 7]), p(&[16, 13]));
assert!(prefer_counting(&mu, &nu), "shape must actually dispatch");
assert_eq!(
crate::strip_lr::AutoLr.schur_product(&mu, &nu),
SkewLr.schur_product(&mu, &nu)
);
}
#[test]
fn multiplicities_match() {
let (mu, nu) = (p(&[4, 3, 2]), p(&[4, 3]));
let got = two_row_product(&mu, &nu).expect("two-row");
let want = SkewLr.schur_product(&mu, &nu);
assert_eq!(got, want);
assert!(
got.iter().any(|(_, c)| *c >= 3),
"expected a coefficient ≥ 3 to make this test meaningful"
);
}
}