StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEven sets of integers
text
Body
copied!<p>Given an array of integers <code>heights</code> I would like to split these into <code>n</code> sets, each with equal <code>totalHeight</code> (sum of the values in set), or as close to as possible. There must be a fixed distance, <code>gap</code>, between each value in a set. Sets do not have to have the same number of values. </p> <p>For example, supposing: </p> <ul> <li><p><code>heights[0, 1, 2, 3, 4, 5] = [120, 78, 110, 95, 125, 95]</code></p></li> <li><p><code>n</code> = 3 </p></li> <li><p><code>gaps</code> = 10 </p></li> </ul> <p>Possible arrangements would be:</p> <ul> <li><p><code>a[0, 1], b[2, 3], c[4, 5]</code> giving <code>totalHeight</code> values of </p> <ul> <li><p><code>a = heights[0] + gap + heights[1] = 120 + 10 + 78 = 208</code> </p></li> <li><p><code>b = heights[2] + gap + heights[3] = 110 + 10 + 95 = 215</code> </p></li> <li><p><code>c = heights[4] + gap + heights[5] = 125 + 10 + 95 = 230</code> </p></li> </ul></li> <li><p><code>a[0], b[1, 2, 3], c[4, 5]</code> giving <code>totalHeight</code> values of </p> <ul> <li><p><code>a = heights[0] = 120</code> </p></li> <li><p><code>b = heights[1] + gap + heights[2] + gap + heights[3] = 303</code> </p></li> <li><p><code>c = heights[4] + gap + heights[5] = 125 + 10 + 95 = 230</code> </p></li> </ul></li> </ul> <p>And so on. I want to find the combination that gives the most evenly-sized sets. So in this example the first combination is better since it gives an overall error of: </p> <pre><code>max - min = 230 - 208 = 22 </code></pre> <p>Whereas the second combination gives an error of 183. I'm trying to do this in JavaScript, but I'm just looking for some sort of outline of an algorithm. Pseudo code or whatever would be great. Any help would be highly appreciated.</p> <p><strong>MY POOR ATTEMPTS:</strong> Obviously one way of solving this would be to just try every possible combination. That would be horrible though once <code>heights</code> gets large. </p> <p>Another method I tried is to get the expected mean height of the sets, calculated as the sum of the values in <code>height</code> / <code>n</code>. Then I tried to fill each set individually by getting as close to this average as possible. It works alright in some cases, but it's too slow.</p> <p><strong>NOTE:</strong> If it helps, I would be happy to have symmetric sets. So for example, with sets (a, b c), a = b. Or with five sets (a, b, c, d, e), a = b and c = d. I think this would be even more difficult to implement but I could be wrong. </p> <p><strong>EDIT:</strong> For anyone who may be interested, the best I could come up with was the following algorithm: </p> <ul> <li>Sort <code>heights</code> in descending order.</li> <li>Create <code>n</code> sets.</li> <li>Put the first <code>n</code> values from <code>heights</code> into the first slot of each set. i.e. put the <code>n</code> largest values at the start of each set. Remove the values from <code>heights</code> as they are added. </li> <li>While <code>heights.count</code> > 0 <ul> <li>Find the smallest <code>totalHeight</code> (including <code>gap</code>) in each of the <code>n</code> sets.</li> <li>Add the next value in <code>heights</code> to this set (and remove the value from <code>heights</code>).</li> </ul></li> <li>Then there's some little algorithm at the end where each set can make <code>x</code> number of swaps with the other sets, if the <code>totalHeight</code> gets closer to the average. I'm keeping <code>x</code> small because this process could go on forever. </li> </ul> <p>It's not terrible, but obviously not perfect. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload