title: How to divide a line of numbers into N groups such that the sums of each group are closest to their mean?
body: <p>I have the following problem: I have M numbers arranged into a line. I need to divide the line into N groups such that the sums of the numbers of each group are closest to the mean of these sums by some metric. The actual metric is not important: we can choose to minimize sum of absolute differences, or variance, etc., depending on which leads to the simplest solution.</p>
  
  <p>A similar problem is partitioning of sets, which is NP Hard. However, here we have additional constraint: groups must pack successive numbers, so there might be a solution that doesn't involve brute-force search. The numbers are large.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Example:</p>
  
  <p>Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups</p>
  
  <p>Let's say we want to minimize sum of absolute differences (SAD).</p>
  
  <p>Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)</p>
  
  <p>Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 &lt;- That's what we want to minimize.</p>