use crate::game::Coalition;
#[derive(Clone, Debug)]
pub struct Span {
dimension: usize,
tolerance: f64,
rows: Vec<(usize, Vec<f64>)>,
}
impl Span {
pub fn new(dimension: usize) -> Span {
Span {
dimension,
tolerance: 1e-9,
rows: Vec::new(),
}
}
pub fn rank(&self) -> usize {
self.rows.len()
}
pub fn is_full(&self) -> bool {
self.rows.len() == self.dimension
}
fn reduce(&self, mut vector: Vec<f64>) -> Vec<f64> {
for (pivot, row) in &self.rows {
let factor = vector[*pivot];
if factor != 0.0 {
for (v, r) in vector.iter_mut().zip(row) {
*v -= factor * r;
}
}
}
vector
}
pub fn contains(&self, vector: &[f64]) -> bool {
self.reduce(vector.to_vec())
.iter()
.all(|v| v.abs() <= self.tolerance)
}
pub fn contains_coalition(&self, coalition: Coalition) -> bool {
self.contains(&indicator(coalition, self.dimension))
}
pub fn insert(&mut self, vector: &[f64]) -> bool {
let reduced = self.reduce(vector.to_vec());
let Some((pivot, &value)) = reduced
.iter()
.enumerate()
.max_by(|a, b| a.1.abs().total_cmp(&b.1.abs()))
else {
return false;
};
if value.abs() <= self.tolerance {
return false;
}
let row: Vec<f64> = reduced.iter().map(|v| v / value).collect();
for (_, existing) in &mut self.rows {
let factor = existing[pivot];
if factor != 0.0 {
for (e, r) in existing.iter_mut().zip(&row) {
*e -= factor * r;
}
}
}
self.rows.push((pivot, row));
true
}
pub fn null_space(&self) -> Vec<Vec<f64>> {
let mut is_pivot = vec![false; self.dimension];
for (pivot, _) in &self.rows {
is_pivot[*pivot] = true;
}
(0..self.dimension)
.filter(|&free| !is_pivot[free])
.map(|free| {
let mut basis = vec![0.0; self.dimension];
basis[free] = 1.0;
for (pivot, row) in &self.rows {
basis[*pivot] = -row[free];
}
basis
})
.collect()
}
pub fn insert_coalition(&mut self, coalition: Coalition) -> bool {
self.insert(&indicator(coalition, self.dimension))
}
}
pub fn solve_square(mut a: Vec<Vec<f64>>, mut b: Vec<f64>, tolerance: f64) -> Option<Vec<f64>> {
let size = b.len();
for column in 0..size {
let pivot =
(column..size).max_by(|&p, &q| a[p][column].abs().total_cmp(&a[q][column].abs()))?;
if a[pivot][column].abs() <= tolerance {
return None;
}
a.swap(column, pivot);
b.swap(column, pivot);
for row in column + 1..size {
let factor = a[row][column] / a[column][column];
if factor != 0.0 {
let (head, tail) = a.split_at_mut(row);
for (target, source) in tail[0][column..].iter_mut().zip(&head[column][column..]) {
*target -= factor * source;
}
b[row] -= factor * b[column];
}
}
}
let mut z = vec![0.0; size];
for row in (0..size).rev() {
let rest: f64 = (row + 1..size).map(|k| a[row][k] * z[k]).sum();
z[row] = (b[row] - rest) / a[row][row];
}
Some(z)
}
pub fn max_abs_difference(a: &[f64], b: &[f64]) -> f64 {
a.iter()
.zip(b)
.map(|(p, q)| (p - q).abs())
.fold(0.0, f64::max)
}
pub fn indicator(coalition: Coalition, dimension: usize) -> Vec<f64> {
(0..dimension)
.map(|i| if coalition.contains(i) { 1.0 } else { 0.0 })
.collect()
}
pub(crate) fn for_each_combination(n: usize, k: usize, visit: &mut impl FnMut(&[usize])) {
fn recurse(
start: usize,
n: usize,
k: usize,
chosen: &mut Vec<usize>,
visit: &mut impl FnMut(&[usize]),
) {
if chosen.len() == k {
visit(chosen);
return;
}
for i in start..n {
if n - i < k - chosen.len() {
break;
}
chosen.push(i);
recurse(i + 1, n, k, chosen, visit);
chosen.pop();
}
}
if k <= n {
recurse(0, n, k, &mut Vec::with_capacity(k), visit);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn tracks_span_of_coalitions() {
let mut span = Span::new(3);
assert!(span.insert_coalition(Coalition::grand(3)));
assert!(span.insert_coalition(Coalition::from_players(&[0, 1])));
assert!(span.contains_coalition(Coalition::singleton(2)));
assert!(!span.contains_coalition(Coalition::singleton(0)));
assert!(!span.insert_coalition(Coalition::singleton(2)));
assert!(span.insert_coalition(Coalition::singleton(0)));
assert!(span.is_full());
}
#[test]
fn null_space_is_orthogonal_to_rows() {
let mut span = Span::new(4);
span.insert(&[1.0, 1.0, 1.0, 1.0]);
span.insert(&[1.0, -1.0, 0.0, 2.0]);
let basis = span.null_space();
assert_eq!(basis.len(), 2);
for z in &basis {
for row in [[1.0, 1.0, 1.0, 1.0], [1.0, -1.0, 0.0, 2.0]] {
let dot: f64 = row.iter().zip(z).map(|(a, b)| a * b).sum();
assert!(dot.abs() < 1e-12);
}
}
}
#[test]
fn solves_square_system() {
let a = vec![vec![0.0, 2.0], vec![1.0, 1.0]];
assert_eq!(solve_square(a, vec![4.0, 3.0], 1e-12), Some(vec![1.0, 2.0]));
let singular = vec![vec![1.0, 1.0], vec![2.0, 2.0]];
assert_eq!(solve_square(singular, vec![1.0, 2.0], 1e-12), None);
}
#[test]
fn combinations() {
let mut seen = Vec::new();
for_each_combination(4, 2, &mut |c| seen.push(c.to_vec()));
assert_eq!(seen.len(), 6);
assert_eq!(seen[0], vec![0, 1]);
assert_eq!(seen[5], vec![2, 3]);
}
}