These remind me of the various rules in social choice theory (Jefferson/D'Hondt, Hamilton, Sainte-Laguë, etc.) for allocating integer numbers of seats based on their proportional vote share. Lots of fun paradoxes there depending on how you do it, most famously (?) the Alabama paradox, in which Alabama would get 8 representatives if there were 299 representatives in the House but only 7 if one more seat was added. Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Feb 2, 2016 at 8:16 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Here's C++ code. The key is the linear-time selection implemented by nth_element. (This code is untested.)
vector<int> quant(const vector<double> &x, int goalsum) { vector<pair<double, int>> a(x.size()) ; // [i] -> (fractionalpart, index) vector<int> r(x.size()) ; size_t total_error = (size_t)goalsum ; for (size_t i=0; i<x.size(); i++) { int f = (int)floor(x[i]*goalsum) ; r[i] = f ; a[i] = make_pair(f-x[i], i) ; total_error -= f ; } nth_element(a.begin(), a.begin()+total_error, a.end()) ; for (size_t i=0; i<total_error; i++) r[a[i].second]++ ; return r ; }
On Tue, Feb 2, 2016 at 5:13 PM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 2, 2016, at 7:53 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Is the MMA algorithm a faithful implementation of Conway and Sloane's algorithm?
The MMA algorithm is O(n log n) due to Ordering[], but there's a well-known linear-time algorithm; certainly Conway and Sloane's algorithm is linear-time?
-tom
from C&S: "The only substantial amount of computation needed is for the sort in Step 3, which takes O(n log n) steps"
My Mma code is doing pretty much exactly what I subsequently saw in your beautifully terse description:
"round, determine total error (say, +e), "e" values to round the other way selecting those with the least individual error”.
How do you identify the “e” elements with least individual error without doing a sort?
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun