0

I have a sorted list of 2000 or fewer objects, each with a numerical value. I'm wondering how I can write (in Java) a way so split this list into sublists, each of roughly 200 objects (with fair leeway) such that the sum of the values of each sublist are roughly equal.

Even if the full list has fewer than 2000 objects, I still want the sublists to be roughly 200 objects each. Thank you!

User9123
  • 69
  • 2
  • 10
  • Yes, sorted by the numerical value from high to low. – User9123 Jul 28 '20 at 19:28
  • 2
    First decide how many lists to make. 2000 / 200 = 10 lists. If you have fewer objects, then `(N / 200)` will give lists of at least 200 objects, and `(N / 200) + 1` will give lists with at most 200 objects. That's assuming the lists are all the same length, but the requirement that all the lists have the same sum may prevent lists of all the same length. The simple greedy algorithm to keep the sums approximately equal: starting from the largest value, add the item to the list with the smallest sum. A priority queue can be used to speed up the process of finding the list with the smallest sum. – user3386109 Jul 28 '20 at 19:34
  • That assumes that the problem has a satisfactory solution. It's possible that there is no solution. For example, let's say you have 1999 items with value `1`, and one item with value `221`. If you create 10 lists with 200 items each, then 9 lists will have a sum of 200, and the other list will have a sum of 420. But if the 10 lists have equal sums (i.e. sum=222), then 9 lists will have 222 items, and the last list will have two items. In short, the two requirements (same number of items, same sum) are self contradictory, and hence no solution will ever be satisfactory for all possible inputs. – user3386109 Jul 28 '20 at 19:57
  • 1
    Thank you for the help! I agree the requirements are contradictory and some concessions will have to be made. Luckily the algorithm is best effort. – User9123 Jul 28 '20 at 20:15

1 Answers1

1

Here is a quick and dirty greedy approach that should work well.

First, decide how many lists you will wind up with. Call that m.

Break your objects into groups of m, with the one possibly smaller group being the values closest to 0.

Order your groups by descending difference between the biggest and the smallest.

Assign your groups to your lists, with the largest object going into the group with the lowest total, the next largest the next lowest, and so on.

When you are done, you will have lists of the right size, with relatively small differences.

(You can do better than this with dynamic programming. But it will also be harder to write. How to constrain items with multiple randomly selected positions so that the average position for each is within a certain range may give you some ideas about how to do that.)

btilly
  • 43,296
  • 3
  • 59
  • 88