[lmi-commits] [lmi] master 56e563c 1/5: Add Hamilton's apportionment algorithm

[Greg Chicares]

branch: master
commit 56e563cf79826159f8aaed797c0e5bd1bc847f65
Author: Gregory W. Chicares <address@hidden>
Commit: Gregory W. Chicares <address@hidden>

    Add Hamilton's apportionment algorithm
---
 report_table.cpp      | 39 +++++++++++++++++++++++++++++++++++++++
 report_table.hpp      |  2 ++
 report_table_test.cpp | 19 +++++++++++++++++++
 3 files changed, 60 insertions(+)

diff --git a/report_table.cpp b/report_table.cpp
index ae2b68f..7d41694 100644
--- a/report_table.cpp
+++ b/report_table.cpp
@@ -25,6 +25,45 @@
 
 #include "alert.hpp"
 #include "math_functions.hpp"           // outward_quotient()
+#include "ssize_lmi.hpp"
+
+#include <numeric>                      // accumulate()
+#include <queue>
+#include <utility>                      // pair
+
+/// Apportion "seats" to "states" by their respective total "votes".
+///
+/// This algorithm is popularly associated with Alexander Hamilton,
+/// who wrote: "as there would commonly be left ... an unapportioned
+/// residue of the total number to be apportioned, it is of necessity
+/// that that residue should be distributed among the several States
+/// by some rule, and none more equal or defensible can be found than
+/// that of giving a preference to the greatest remainders".
+///
+/// A fascinating geometric analysis is to be found in B.A. Bradberry,
+/// "A Geometric View of Some Apportionment Paradoxes", 65 Mathematics
+/// Magazine 1, 16 (1992).
+
+std::vector<int> apportion(std::vector<int> const& votes, int total_seats)
+{
+    int const cardinality = lmi::ssize(votes);
+    std::vector<int> seats(cardinality);
+    int const total_votes = std::accumulate(votes.begin(), votes.end(), 0);
+    std::priority_queue<std::pair<int,int>> queue;
+    for(int j = 0; j < cardinality; ++j)
+        {
+        seats[j]            = (votes[j] * total_seats) / total_votes;
+        int const remainder = (votes[j] * total_seats) % total_votes;
+        queue.push({remainder, j});
+        }
+    int const dealt_seats = std::accumulate(seats.begin(), seats.end(), 0);
+    for(int j = 0; j < total_seats - dealt_seats; ++j)
+        {
+        ++seats[queue.top().second];
+        queue.pop();
+        }
+    return seats;
+}
 
 /// Compute column widths.
 ///
diff --git a/report_table.hpp b/report_table.hpp
index d11cab9..f89ef5d 100644
--- a/report_table.hpp
+++ b/report_table.hpp
@@ -103,6 +103,8 @@ class LMI_SO table_column_info
     bool          const is_elastic_;
 };
 
+std::vector<int> LMI_SO apportion(std::vector<int> const& votes, int seats);
+
 void LMI_SO set_column_widths
     (int                             total_width
     ,int                             column_margin
diff --git a/report_table_test.cpp b/report_table_test.cpp
index a9ac690..b3261c8 100644
--- a/report_table_test.cpp
+++ b/report_table_test.cpp
@@ -88,6 +88,7 @@ class report_table_test
   public:
     static void test()
         {
+        test_apportion();
         test_bloat();
         test_generally();
         test_group_quote();
@@ -95,12 +96,30 @@ class report_table_test
         }
 
   private:
+    static void test_apportion();
     static void test_bloat();
     static void test_generally();
     static void test_group_quote();
     static void test_illustration();
 };
 
+void report_table_test::test_apportion()
+{
+    // Test cases from:
+    //   https://en.wikipedia.org/wiki/Largest_remainder_method
+
+    std::vector<int> const votes0 = {47000, 16000, 15800, 12000, 6100, 3100};
+    std::vector<int> const seats0 = {5, 2, 1, 1, 1, 0};
+    BOOST_TEST(seats0 == apportion(votes0, 10));
+
+    std::vector<int> const votes1 = {1500, 1500, 900, 500, 500, 200};
+    std::vector<int> const seats1 = {7, 7, 4, 3, 3, 1};
+    BOOST_TEST(seats1 == apportion(votes1, 25));
+
+    std::vector<int> const seats2 = {8, 8, 5, 2, 2, 1};
+    BOOST_TEST(seats2 == apportion(votes1, 26));
+}
+
 void report_table_test::test_bloat()
 {
     std::vector<table_column_info> const v =