use std::fmt;
use crate::error::{Error, Result};
const CAPACITY: usize = 64;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Coalition(pub u64);
impl Coalition {
pub const fn empty() -> Coalition {
Coalition(0)
}
pub fn grand(n: usize) -> Coalition {
assert!(n <= CAPACITY, "Coalition は 64 人まで ({n} 人)");
Coalition(if n == 0 { 0 } else { u64::MAX >> (64 - n) })
}
pub fn singleton(player: usize) -> Coalition {
Coalition(bit(player))
}
pub fn from_players(players: &[usize]) -> Coalition {
Coalition(players.iter().fold(0, |mask, &i| mask | bit(i)))
}
pub fn try_from_players(n: usize, players: &[usize]) -> Result<Coalition> {
let limit = n.min(CAPACITY);
match players.iter().find(|&&i| i >= limit) {
Some(&i) if i < n => Err(Error::InvalidArgument(format!(
"プレイヤー番号 {i} は Coalition で扱える範囲 (64 未満) を超える"
))),
Some(i) => Err(Error::InvalidArgument(format!(
"プレイヤー番号 {i} が人数 {n} 以上"
))),
None => Ok(Coalition::from_players(players)),
}
}
pub(crate) fn embed(members: &[usize], sub: u64) -> Coalition {
Coalition(
members
.iter()
.enumerate()
.filter(|(bit, _)| sub >> bit & 1 == 1)
.fold(0, |mask, (_, &i)| mask | 1 << i),
)
}
pub(crate) fn union_of(parts: &[Coalition], chosen: u64) -> Coalition {
Coalition(
parts
.iter()
.enumerate()
.filter(|(bit, _)| chosen >> bit & 1 == 1)
.fold(0, |mask, (_, c)| mask | c.0),
)
}
pub fn contains(self, player: usize) -> bool {
player < CAPACITY && self.0 >> player & 1 == 1
}
pub fn len(self) -> usize {
self.0.count_ones() as usize
}
pub fn is_empty(self) -> bool {
self.0 == 0
}
pub fn insert(&mut self, player: usize) {
self.0 |= bit(player);
}
pub fn remove(&mut self, player: usize) {
if player < CAPACITY {
self.0 &= !(1u64 << player);
}
}
pub fn union(self, other: Coalition) -> Coalition {
Coalition(self.0 | other.0)
}
pub fn intersection(self, other: Coalition) -> Coalition {
Coalition(self.0 & other.0)
}
pub fn is_subset(self, other: Coalition) -> bool {
self.0 & !other.0 == 0
}
pub fn complement(self, n: usize) -> Coalition {
Coalition(Coalition::grand(n).0 & !self.0)
}
pub fn index(self) -> usize {
self.0 as usize
}
pub fn members(self) -> impl Iterator<Item = usize> {
let mut rest = self.0;
std::iter::from_fn(move || {
if rest == 0 {
return None;
}
let player = rest.trailing_zeros() as usize;
rest &= rest - 1;
Some(player)
})
}
pub fn sum(self, x: &[f64]) -> f64 {
self.members().map(|i| x[i]).sum()
}
}
fn bit(player: usize) -> u64 {
assert!(
player < CAPACITY,
"Coalition のプレイヤー番号は 64 未満 ({player})"
);
1u64 << player
}
impl fmt::Display for Coalition {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write_members(f, self.members())
}
}
pub(crate) fn write_members(
f: &mut fmt::Formatter<'_>,
members: impl Iterator<Item = usize>,
) -> fmt::Result {
let members: Vec<String> = members.map(|i| i.to_string()).collect();
f.pad(&format!("{{{}}}", members.join(", ")))
}
pub(crate) fn players_from_len(len: usize) -> Result<usize> {
let size = len.checked_add(1).ok_or(Error::InvalidLength(len))?;
if len == 0 || !size.is_power_of_two() {
return Err(Error::InvalidLength(len));
}
Ok(size.trailing_zeros() as usize)
}
pub(crate) fn lexicographic_order(n: usize) -> Vec<Coalition> {
let mut order = Vec::with_capacity((1usize << n) - 1);
let mut members = Vec::with_capacity(n);
for size in 1..=n {
push_combinations(n, size, 0, &mut members, &mut order);
}
order
}
fn push_combinations(
n: usize,
size: usize,
first: usize,
members: &mut Vec<usize>,
out: &mut Vec<Coalition>,
) {
if members.len() == size {
out.push(Coalition::from_players(members));
return;
}
let remaining = size - members.len();
for player in first..=(n - remaining) {
members.push(player);
push_combinations(n, size, player + 1, members, out);
members.pop();
}
}
pub(crate) fn lex_to_binary(values: &[f64]) -> Result<Vec<f64>> {
let n = players_from_len(values.len())?;
let mut binary = vec![0.0; values.len()];
for (value, coalition) in values.iter().zip(lexicographic_order(n)) {
binary[coalition.index() - 1] = *value;
}
Ok(binary)
}
pub fn binary_to_lex(values: &[f64]) -> Result<Vec<f64>> {
let n = players_from_len(values.len())?;
Ok(lexicographic_order(n)
.into_iter()
.map(|coalition| values[coalition.index() - 1])
.collect())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn lexicographic_order_for_three_players() {
let order: Vec<Vec<usize>> = lexicographic_order(3)
.into_iter()
.map(|s| s.members().collect())
.collect();
assert_eq!(
order,
vec![
vec![0],
vec![1],
vec![2],
vec![0, 1],
vec![0, 2],
vec![1, 2],
vec![0, 1, 2]
]
);
}
#[test]
fn lex_binary_round_trip() {
let lex: Vec<f64> = (1..=31).map(f64::from).collect();
let binary = lex_to_binary(&lex).unwrap();
assert_eq!(binary_to_lex(&binary).unwrap(), lex);
assert_eq!(binary[2], 6.0);
}
#[test]
fn rejects_invalid_length() {
assert_eq!(players_from_len(6), Err(Error::InvalidLength(6)));
assert_eq!(players_from_len(7), Ok(3));
}
}