2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ "Suppose we have an array A[1...n]" ​ For i=0 to nif A[i]==K ​ ​ ​ ​ $\endgroup$ – user12859 Feb 10 '17 at 19:39
  • 1
    $\begingroup$ Regardless of my above comment, I believe [2,2,3,3] is a simpler case in which your algorithm's output is suboptimal. ​ ​ $\endgroup$ – user12859 Feb 10 '17 at 20:02
  • $\begingroup$ @RickyDemer K is the highest value in the array, so in this case I'm putting all the max value items in one subset and all other elements in the other subset. But in your second comment you are indeed correct. It would be easy to fix, but I think that once it is fixed for your example, it will perform suboptimally in the example I have in the OP $\endgroup$ – Luca Giorgi Feb 10 '17 at 20:25
  • $\begingroup$ "A[1...n]"would seem to indicate that when i=0, i is not a valid index to A. ​ ​ $\endgroup$ – user12859 Feb 10 '17 at 20:31
  • 1
    $\begingroup$ Now that you know the answer to your question, would you like to write an answer to your own question, so that this is treated as answered? For more background, you can take a look at en.wikipedia.org/wiki/Partition_problem. There are counterexamples showing that the obvious greedy algorithm doesn't work: en.wikipedia.org/wiki/Partition_problem#The_greedy_algorithm. See also cs.stackexchange.com/q/63882/755. $\endgroup$ – D.W. Feb 10 '17 at 23:26
3
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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)

Source :https://www.youtube.com/watch?v=XafGZHCxdc0

$\endgroup$
  • 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 Mar 26 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.