Sorting Algorithm?

[Slurmp]

I was looking to sort a set of values into X number of subsets of size Y so that the mean of each subset is as close as possible to the mean of the parent set

Does anyone know offhand of a program out there that could do this?

Thanks!

[Granger]

Try this?

[Slurmp]

Try this?

Thanks, I'm checking other places as well. I was just curious if someone here has used an app to sort items this way for the game.

[Potjeh]

Wouldn't a good enough heuristic for this be just taking elements alternatively from the start and the end of a sorted list? Frankly I don't see how you could get better results while preserving the rule of all subsets having the same number of elements.

[loftar]

To begin with, it should be noted that "as close as possible" is possible to define in several different ways, so let's assume we're talking about a sum-of-square-errors metric for the sake of simplicity.

Depending on your number of values and subsets, the brute-force solution may not actually be out of reach. If n is the number of values, and k is the number of subsets of m values each (such that m * k = n), the total number of ways to partition the values into subsets is

eq1.png

Which simplifies into

eq2.png

For either relatively small numbers of n, or small numbers of k, this might come out to reasonable values for exhaustive search.

Though for many values, of course, it doesn't. It's still possible to do heuristically better than Potjeh's suggestion, however. I tried that with 500 random numbers between 100 and 200, divided into 20 subsets, and the initial sum-of-square-errors was ~36.1. After applying a simple and fast adjustment algorithm, however, I decreased it to ~0.08. The algorithm in question simply being as such:

• For each distinct pair (a, b) of subsets of values:
•     For each pair of items (i, j) in (a, b):
•         If swapping i and j between a and b decreases the global error, then do so.

As is clear from the above description, this algorithm scales simply with O(n²), which should be not only realistic but even fast for any realistic values of n. It isn't strictly optimal, though, because it's often possible to optimize the error more by running the adjustment again, but it stabilizes very quickly (within two runs for every set I've tried it on thus far). I'm not sure if I can formally prove that the solution is optimal once it has stabilized, however. Though I'd think it is.

[Potjeh]

Oh LOL, I was only thinking of two member subsets

But yeah, I think my heuristic can still give reasonable results if subset size is a power of two in which case you just apply my method recursively. Won't get as good results, but I think it'd be faster. Of course, accuracy is wildly dependant on values spread. If they're all reasonably close it should be fine, and I suspect this is for dividing trade items into chests of roughly equal quality so values should be fairly close to eachother.