custom partition problem

Question

Could some one guide me on how to solve this problem.

We are given a set S with k number of elements in it.

Now we have to divide the set S into x subsets such that the difference in number of elements in each subset is not more than 1 and the sum of each subset should be as close to each other as possible.

Example 1: {10, 20, 90, 200, 100} has to be divided into 2 subsets

Solution:{10,200}{20,90,100}

sum is 210 and 210

Example 2: {1, 1, 2, 1, 1, 1, 1, 1, 1, 6}

Solution:{1,1,1,1,6}{1,2,1,1,1}

Sum is 10 and 6.

not homework, there is this programming competition on techgig, i have just stripped down their question. — yahh, Jul 21 '11 at 17:10
1<=k<=10000, 1<=x<=1000 and variables inside the subset can be 1<=E<=1000 — yahh, Jul 21 '11 at 17:14

score 2 · Accepted Answer · answered Jul 21 '11 at 20:59

I see a possible solution in two stages.

Stage One

Start by selecting the number of subsets, N. Sort the original set, S, if possible. Distribute the largest N numbers from S into subsets 1 to N in order. Distribute the next N largest numbers from S the subsets in reverse order, N to 1. Repeat until all numbers are distributed.

If you can't sort S, then distribute each number from S into the subset (or one of the subsets) with the least entries and the smallest total.

You should now have N subsets all sized within 1 of each other and with very roughly similar totals.

Stage Two

Now try to refine the approximate solution you have. Pick the largest total subset, L, and the smallest total subset, M. Pick a number in L that is smaller than a number in M but not by so much as to increase the absolute difference between the two subsets. Swap the two numbers. Repeat. Not all pairs of subsets will have swappable numbers. Each swap keeps the subsets the same size.

If you have a lot of time you can do a thorough search; if not then just try to pick off a few obvious cases. I would say don't swap numbers if there is no decrease in difference; otherwise you might get an infinite loop.

You could interleave the stages once there are at least two members in some subsets.

Ricky Bobby · Answer 2 · 2011-07-22T07:32:46.663

There is no easy algorithm for this problem.

Check out the partition problem also known as the easiest hard problem , that solve this for 2 sets. This problem is NP-Complete, and you should be able to find all the algorithms to solve it on the web

I know your problem is a bit different since you can chose the number of sets, but you can inspire yourself from solutions to the previous one.

For example :

You can transform this into a serie of linear programs, let k be the number of element in your set.

{a1 ... ak} is your set

For i = 2 to k:

   try to solve the following program:
        xjl = 1 if element j of set is in set number l (l <= i) and 0 otherwise

        minimise max(Abs(sum(apxpn) -sum(apxpm)) for all m,n) // you minimise the max of the difference between 2 sets.

        s.t 
        sum(xpn) on n = 1
        (sum(xkn) on k)-(sum(xkm) on k) <= 1 for all m n // the number of element in 2 list are different at most of one element.
        xpn in {0,1}

  if you find a min less than one    then stop
  otherwise continue

end for

Hope my notations are clear.

The complexity of this program is exponential, and if you find a polynomial way to solve this you would probe P=NP so I don't think you can do better.

EDIT

I saw you comment ,I missunderstood the constraint on the size of the subsets (I thought it was the difference between 2 sets) I don't I have time to update it I will do it when I have time. sryy

EDIT 2

I edited the linear program and it should do what it's asked to do. I just added a constraint.

Hope this time the problem is fully understood, even though this solution might not be optimal

It's quite a bit different: in this case, the sizes of the subsets can only differ by at most 1. I don't think this answer is helpful in its current form. The wikipedia article does mention this condition, but gives no indication on how to handle it. Plus, just having more than two subsets significantly changes the game. — IVlad, Jul 21 '11 at 17:18
OK I misread the text, I guess you could easily work on my solution to get a one that works. just change the constraints of the linear program. I will try to update it later. — Ricky Bobby, Jul 21 '11 at 17:27
@IVlad I edited the program so it respects all the constraints. Thx for your comment I missread the question first — Ricky Bobby, Jul 22 '11 at 07:35

score 0 · Answer 3 · answered Jul 21 '11 at 17:29

I'm no scientist, so I'd try two approaches:

After sorting items, then going from both "ends" and moving first and last to the actual set,then shift to next set, loop;

Then:

Checking the differences of sums of the sets, and shuffling items if it would help.
Coding the resulting sets appropriately and trying genetic algorithms.

custom partition problem

3 Answers3

Linked