title: How to round floats to integers while preserving their sum?
body: <p>Let's say I have an array of floating point numbers, in sorted (let's say ascending) order, whose sum is known to be an integer <code>N</code>. I want to "round" these numbers to integers while leaving their sum unchanged. In other words, I'm looking for an algorithm that converts the array of floating-point numbers (call it  <code>fn</code>) to an array of integers (call it <code>in</code>) such that:</p>
  
  <ol>
  <li>the two arrays have the same length</li>
  <li>the sum of the array of integers is <code>N</code></li>
  <li>the difference between each floating-point number <code>fn[i]</code> and its corresponding integer <code>in[i]</code> is less than 1 (or equal to 1 if you really must)</li>
  <li>given that the floats are in sorted order (<code>fn[i] &lt;= fn[i+1]</code>), the integers will also be in sorted order (<code>in[i] &lt;= in[i+1]</code>)</li>
  </ol>
  
  <p>Given that those four conditions are satisfied, an algorithm that minimizes the rounding variance (<code>sum((in[i] - fn[i])^2)</code>) is preferable, but it's not a big deal.</p>
  
  <p>Examples:</p>
  
  <pre>
  [0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14]
      => [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
  [0.1, 0.3, 0.4, 0.4, 0.8]
      => [0, 0, 0, 1, 1]
  [0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
      => [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
  [0.4, 0.4, 0.4, 0.4, 9.2, 9.2]
      => [0, 0, 1, 1, 9, 9] is preferable
      => [0, 0, 0, 0, 10, 10] is acceptable
  [0.5, 0.5, 11]
      => [0, 1, 11] is fine
      => [0, 0, 12] is technically not allowed but I'd take it in a pinch
  </pre>
  
  <p>To answer some excellent questions raised in the comments:</p>
  
  <ul>
  <li>Repeated elements are allowed in both arrays (although I would also be interested to hear about algorithms that work only if the array of floats does not include repeats)</li>
  <li>There is no single correct answer - for a given input array of floats, there are generally multiple arrays of ints that satisfy the four conditions.</li>
  <li>The application I had in mind was - and this is kind of odd - distributing points to the top finishers in a game of MarioKart ;-) Never actually played the game myself, but while watching someone else I noticed that there were 24 points distributed among the top 4 finishers, and I wondered how it might be possible to distribute the points according to finishing time (so if someone finishes with a large lead they get a larger share of the points). The game tracks point totals as integers, hence the need for this kind of rounding.</li>
  </ul>
  
  <hr>
  
  <p>For the curious, here is <a href="http://static.ellipsix.net/ext-tmp/roundingtest.py" rel="noreferrer">the test script</a> I used to identify which algorithms worked.</p>