The Problem
Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=[1,3,1,1], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.
My Solution (In pseudocode)
For i=0 to n
if A[i]==K //If this element is the highest element in the array, put it in Sy
Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
go=false
//Move the smallest element from the biggest group to the other one
if Sx>Sy
SyTemp = Sy + min(Sx)
SxTemp = Sx - min(Sx)
else if Sy>Sx
SxTemp = Sx + min(Sy)
SyTemp = Sy - min(Sy)
//if this improves on our min, save it and check for another iteration
if |SxTemp-SyTemp|<min
Sx=SxTemp
Sy=SyTemp
min = |Sx-Sy|
go=true
else
Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)
My question
Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.
the example he gave me to prove that these edge cases exist was [1,2,5,5] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).
2 Answers 2
My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example [2,2,3,3], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering). Altough this flaw could be fixed in my code, it would then perform suboptimally in the example my professore had given me (And that I wrote in the OP).
A good greedy version of the algorithm is given on Wikipedia and is as follows:
def find_partition(int_list):
"returns: An attempt at a partition of `int_list` into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
if sum(A) < sum(B):
A.add(n)
else:
B.add(n)
return (A, B)
This approach gives a 7⁄6-approximation of the optimal solution, thus the only viable technique to use in case you need an optimal algorithm is dynamic programming. An implementation can be found, again, on Wikipedia and will run in pseudo-polynomial time.
This will help to get the subset
numbers=[5,6,1,11]
numbers.sort(reverse = True)
total=sum(numbers)/2
S1=[]
S2=[]
for i in numbers:
if(i+sum(S1)-total)<0:
S1.append(i)
else:
S2.append(i)
print ('S1' ,S1)
print ('S2',S2)
-
1$\begingroup$ This solution is incorrect. For example, it would return [1,2] and [2,3] for [1,2,2,3], while the optimal solution are [1,3] and [2,2]. In addition, the question is asking for a correctness analysis of the OP's algorithm, not asking for another solution. I'm not sure if this is really an answer. $\endgroup$xskxzr– xskxzr2019年03月26日 03:59:22 +00:00Commented Mar 26, 2019 at 3:59
Explore related questions
See similar questions with these tags.
For i=0 to nif A[i]==K $\endgroup$i=0,iis not a valid index toA. $\endgroup$