Splitting values into groups evenly

Question

Let me try to explain the situation the best I can.

Lets say I have 3 values

1, 2, 3

I tell an algorithm to split this values into x columns. Lets say x = 2 for clarification.

The algorithm determines that the group of values is best put into two columns the following way.

1st column    2nd column
---------------------------
1             3
2

Each column has an even number (totals, not literals) value.

Now lets say I have the following values

7, 8, 3, 1, 4

I tell the algorithm that I want the values split into 3 columns. The algorithm now tells me that the following is the best fit.

1st column    2nd column    3rd column
8             7             3
              1             4

Notice how the columns arent quiet even, but it is as close as it can get. A little over and a little under is considered ok, as long as the list is AS CLOSE TO EVEN AS IT CAN BE.

Anybody got any suggestions? Know any good methods of doing this?

Answer 1

If you want exact same values, then for number of columns x=2, it is the classic Partition Problem which is NP-Complete, but has pseudo polynomial solutions.

Any more columns (i.e. x>2), and it becomes strongly NP-Complete. 3-Partition Problem.

For x > 3, I suspect it will still be strongly NP-Complete.

Since the x-partition problem can be reduced to your problem, it is going to be as hard as the above problems.

You would probably need some heuristic methods to help you out.

Answer 2

I would do it like this:

• add all the values, let's call this S
• divide S by the number of columns, let's call this M.
• find a set of values of which the sum is M or as close as possible to M, using a knapsack algorithm (e.g. http://search.cpan.org/~andale/Algorithm-Knapsack-0.02/lib/Algorithm/Knapsack.pm (just a quick Google on knapsack))
• take the sum of the set of values and subtract it from S, let's call it T.
• divide T by the number of columns minus 1
• and repeat the algorithm

Answer 3

I answered a similar question a while back.

I can think of a greedy sub optimal solution.

1. Sort the numbers decreasing order order. (smaller numbers surprise less so deal them later)
2. Decide on the number of sets you are going to have. not too sure about this
3. Go through the set elements one by one and put them into the subset which has the lowest sum (round robin in case of equal sums)

This is never going to give you the optimal solution though.

For your case, 8 7 4 3 1 would be the order. And you would (luckily) get the same results as you've mentioned.

8 = 8

7 1 = 8

4 3 = 7

This will not always give you the optimal solution