StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Your second approach - finding the mean (height / n), then attempting to fill sets with a mean as close as possible seems like a good practical approach. You say this is too slow... the following implementation is O(n*m log n) where m is the maximum number of elements allowed in a set. If m can be very large, then this could be quite slow, however if m is constrained to be within a certain range then it could approach O(n log n) which is about as fast as you are going to get.</p> <pre><code> Find the mean height of all values. h_mean = Sum(h) / n; O(n). Sort all heights. O(n log n). Examine the highest and lowest height. Add the value which is furthest from the mean to a new set. Remove this value from the sorted heights. Repeat for max_number allowed in set = 1 .. m (m < n / 2) { Repeat: { If the set mean is higher than the mean. Add the lowest value from the sorted heights. Remove this value from the sorted heights. If the set mean is lower than the mean Add the highest value from the sorted heights. Remove this value from the sorted heights. Recalculate the set mean (taking account of the gap). If the new set mean is further from the h_mean than the last OR If the set has too many elements break } Until all numbers are used. Keep track of the standard deviations for this assignment. If this assignment is the best so far, keep it. } </code></pre> <p>This isn't going to give a provably optimal solution, but it's simple and that has a lot going for it...</p> <p>Note, in this algorithm, all sets have the same number of elements, m. You repeat an iteration for different values of m, say, 2, 3, 4 (note that m should be a factor of N). Each set ends up with approximately m * mean_height for total height. </p> <p><em>You may ask, well what if N is prime?</em> </p> <p>Then clearly, one set will value short on total value. </p> <p><em>Does this mean this algorithm is useless?</em></p> <p>Not at all. It's simple and it should produce a good first attempt at a solution. You may wish to use this algorithm first, then refine the first result using optimization techniques (such as selective swapping of heights being sets). </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