use std::cmp::Ordering;
use std::collections::BinaryHeap;
use super::PlayerSet;
struct Candidate {
cost: f64,
sequence: u64,
last: usize,
toggled: Vec<usize>,
}
impl PartialEq for Candidate {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}
impl Eq for Candidate {}
impl PartialOrd for Candidate {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Candidate {
fn cmp(&self, other: &Self) -> Ordering {
other
.cost
.total_cmp(&self.cost)
.then(other.sequence.cmp(&self.sequence))
}
}
pub struct SubsetsByWeight {
players: usize,
best: PlayerSet,
best_sum: f64,
order: Vec<usize>,
costs: Vec<f64>,
heap: BinaryHeap<Candidate>,
sequence: u64,
started: bool,
}
impl SubsetsByWeight {
pub fn new(weights: &[f64], offset: f64) -> SubsetsByWeight {
let players = weights.len();
let mut best = PlayerSet::empty(players);
let mut best_sum = offset;
for (i, &w) in weights.iter().enumerate() {
if w > 0.0 {
best.insert(i);
best_sum += w;
}
}
let mut order: Vec<usize> = (0..players).collect();
order.sort_by(|&a, &b| {
weights[a]
.abs()
.total_cmp(&weights[b].abs())
.then(a.cmp(&b))
});
let costs: Vec<f64> = order.iter().map(|&i| weights[i].abs()).collect();
SubsetsByWeight {
players,
best,
best_sum,
order,
costs,
heap: BinaryHeap::new(),
sequence: 0,
started: false,
}
}
fn push(&mut self, cost: f64, last: usize, toggled: Vec<usize>) {
self.sequence += 1;
self.heap.push(Candidate {
cost,
sequence: self.sequence,
last,
toggled,
});
}
}
impl Iterator for SubsetsByWeight {
type Item = (PlayerSet, f64);
fn next(&mut self) -> Option<Self::Item> {
if !self.started {
self.started = true;
if self.players > 0 {
self.push(self.costs[0], 0, vec![0]);
}
return Some((self.best.clone(), self.best_sum));
}
let candidate = self.heap.pop()?;
let j = candidate.last;
if j + 1 < self.players {
let mut added = candidate.toggled.clone();
added.push(j + 1);
self.push(candidate.cost + self.costs[j + 1], j + 1, added);
let mut replaced = candidate.toggled.clone();
*replaced.last_mut().expect("空でない") = j + 1;
self.push(
candidate.cost - self.costs[j] + self.costs[j + 1],
j + 1,
replaced,
);
}
let mut set = self.best.clone();
for &k in &candidate.toggled {
set.toggle(self.order[k]);
}
Some((set, self.best_sum - candidate.cost))
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn enumerates_all_subsets_in_order() {
let weights = [3.0, -1.0, 0.5, -2.5, 2.0, 0.0];
let all: Vec<(PlayerSet, f64)> = SubsetsByWeight::new(&weights, 1.5).collect();
assert_eq!(all.len(), 64);
assert!(all.windows(2).all(|w| w[0].1 >= w[1].1 - 1e-12));
let distinct: std::collections::HashSet<_> = all.iter().map(|(s, _)| s.clone()).collect();
assert_eq!(distinct.len(), 64);
for (set, sum) in &all {
let expected: f64 = 1.5 + set.members().map(|i| weights[i]).sum::<f64>();
assert!((sum - expected).abs() < 1e-12);
}
}
}