A partition of a into k A disjoint subset

Question

Give a set S , divide it into k disjoint subsets so that the difference of their sums is minimal.

say, S = {1,2,3,4,5} and k = 2 , therefore { {3,4}, {1,2,5} } , since their sums {7,8} have a minimal difference. For S = {1,2,3}, k = 2 it will be {{1,2},{3}} , since the difference in the sum is 0 .

The problem is similar to the problem in the section in the Algorithm Design Guide. In addition, Stephen Skien discusses a solution method without adjustment.

I was going to try Simulated Annealing. So I wonder if there was a better way?

Thanks in advance.

Answer 1

For k=2 you can use the pseudo-field algorithm for the backpack. The best we can do is sum (S) / 2. Run the knapsack algorithm

 for s in S: for i in 0 to sum(S): if arr[i] then arr[i+s] = true; 

then look at the sum (S) / 2, and then the sum (S) / 2 +/- 1, etc.

For 'k> = 3', I think this is NP-complete, like a 3-partition problem.

The easiest way to do this with k> = 3 is to simply overdo it, here is one way, I'm not sure if this is the fastest or cleanest.

 import copy arr = [1,2,3,4] def t(k,accum,index): print accum,k if index == len(arr): if(k==0): return copy.deepcopy(accum); else: return []; element = arr[index]; result = [] for set_i in range(len(accum)): if k>0: clone_new = copy.deepcopy(accum); clone_new[set_i].append([element]); result.extend( t(k-1,clone_new,index+1) ); for elem_i in range(len(accum[set_i])): clone_new = copy.deepcopy(accum); clone_new[set_i][elem_i].append(element) result.extend( t(k,clone_new,index+1) ); return result print t(3,[[]],0); 

Simulated annealing may be good, but since the "neighbors" of a particular solution are not entirely understood, the genetic algorithm may be better suited for this. You will begin to randomly select a group of subsets and “mutate” by moving numbers between the subsets.

Answer 2

If the sets are large, I would definitely go for a stochastic search. I don’t know exactly what spinning_plate means when writing that "the region is not clearly defined." Of course, you either move one element from one set to another, or change objects from two different sets, and this is a simple area. I would use both operations in stochastic search (in practice, it can be a taboo search or simulated annealing.)