largest_remainder_method/
lib.rs

1use std::cmp::Ordering;
2
3pub fn apportion(votes: &[u64], seat_number: u64) -> Vec<u64> {
4    let total: u64 = votes.iter().sum();
5    let hare_quota = total as f64 / seat_number as f64;
6
7    let votes_quota: Vec<f64> = votes
8        .iter()
9        .map(|vote| (*vote as f64) / hare_quota)
10        .collect();
11
12    // calculate automatic seats first
13    let mut seats: Vec<u64> = votes_quota.iter().map(|v| v.floor() as u64).collect();
14
15    let mut remainders: Vec<(f64, u64)> = votes_quota
16        .iter()
17        .enumerate()
18        .map(|(i, v)| (v.fract(), i as u64))
19        .collect();
20
21    let total_seat: u64 = seats.iter().sum();
22    let remaining_seat: u64 = seat_number - total_seat;
23
24    remainders.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(Ordering::Equal));
25    remainders.reverse();
26
27    let highest_remainder_seats: Vec<u64> = remainders
28        .iter()
29        .take(remaining_seat as usize)
30        .map(|v| v.1)
31        .collect();
32
33    for index in highest_remainder_seats {
34        seats[index as usize] += 1;
35    }
36
37    seats
38}
39
40// https://en.wikipedia.org/wiki/Largest_remainder_method#Examples
41#[cfg(test)]
42mod tests {
43    use super::apportion;
44
45    #[test]
46    fn test_apportion() {
47        let votes = vec![47_000, 16_000, 15_800, 12_000, 6_100, 3_100];
48        let seats = 10;
49        let total_seats = apportion(&votes, seats);
50        assert_eq!(vec![5, 2, 1, 1, 1, 0], total_seats);
51    }
52
53    #[test]
54    fn test_apportion_again() {
55        let votes = vec![1500, 1500, 900, 500, 500, 200];
56        let seats = 25;
57        let total_seats = apportion(&votes, seats);
58        assert_eq!(vec![7, 7, 4, 3, 3, 1], total_seats);
59
60        let new_seats = 26;
61        let new_total_seats = apportion(&votes, new_seats);
62        assert_eq!(vec![8, 8, 5, 2, 2, 1], new_total_seats);
63    }
64}
largest_remainder_method/lib.rs

largest_remainder_method/
lib.rs
