3

after reading about Finding three elements in an array whose sum is closest to a given number, this is my attempt at implementing such algorithm

def findThree(seq, goal):

    # initialize the differences 
    goalDifference = float("inf")
    dl = -1
    dr = -1
    dx = -1

    for x in range(len(seq)-1):

        left = x+1
        right = len(seq)-1


        while (left < right):

            # if the absolute value of the previous set and the goal is less than the current goalDifference,
            # keep track of the new set
            if(abs(goal - (seq[left] + seq[right] + seq[x])) < goalDifference):
                dl = left
                dr = right
                dx = x

            tmp = seq[left] + seq[right] + seq[x]

            if tmp > goal:
                right -= 1
            elif tmp < goal:
                left += 1
            else:
                return [seq[left],seq[right],seq[x]]

    # if no match is found, return the closest set
    return [seq[dl],seq[dr], seq[dx]]

The algorithm works great for finding exact solutions, given 

arr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320]

findThree(arr, 349) // want to get [120, 140, 89]
>> [120, 140 89] // success

findThree(arr, 439) // want to get [140, 179, 120]
>> [140, 179,120] // success

however, when I want to see if it'll return the closest, it returns

findThree(arr, 350) // only 1 more than 349, should return [120, 140, 89]
>> [320, 320, 259] // fail

findThree(arr, 440) // only 1 more than 439, should return [140, 179, 120]
>> [320, 320, 259] // fail

it appears that when I want it to return the "cloest" element, it always returns [320, 320, 259]. I've been looking at the code for a few hours now, but still can't figure out what's wrong.

Community
  • 1
  • 1
user3277633
  • 1,891
  • 6
  • 28
  • 48

3 Answers3

4

I quickly looked through your code, the main problem is that the "goal difference" was never changed.

You need to squeeze the "goal difference" as you go, otherwise all combinations are within the "goal difference", obviously you will end up having the last set as the answer.

Peter Pei Guo
  • 7,770
  • 18
  • 35
  • 54
  • hmm I am not quite sure I get what you're suggesting. In the parameters, goal is the final sum that I'd like to get as close to as possible – user3277633 Sep 21 '14 at 19:53
  • That's great, enjoy! – Peter Pei Guo Sep 21 '14 at 20:03
  • for some reason I used the same approach in my findTwo(), also without updating goaldifferences, but somehow it worked magically. Guess that's why I completely forgot about the updating part – user3277633 Sep 21 '14 at 20:05
0

You could do something like:

def find3(tgt, arr):
    lowest=[float('inf')]
    for i in range(0,len(arr)-2):
        j=i+1
        k=len(arr)-1
        while k>=j:
            t=tuple(arr[x] for x in (i, j, k) )
            sum_t=sum(t)
            if sum_t==tgt:
                return t
            elif sum_t<sum(lowest):
                lowest=t     
            if sum_t>0:
                k-=1
            else:
                j+=1                    

    return lowest

Which works for all cases you describe.

dawg
  • 98,345
  • 23
  • 131
  • 206
0

Actually, the problem here is that you are not keeping track of the closest combination of numbers. As per the current algorithm your code checks the combination till left = right-1 and x=left-1 (since left = x+1); . At the end of the execution of loop, you will have x=259, left=320 and right=320 always, if the correct combination is not achieved. thats why its returning the values of last iteration always i.e [320, 320, 259], when findThree(arr, 350) and findThree(arr, 440) were called. A solution may be to take three variable close1 close2 and close3 and initialize them to 0 before the start of for loop;and within for loop add following after the if statement:

if(abs(goal - (seq[left] + seq[right] + seq[x])) < abs(goal - (close1 + close2 + close3)) ):
close1 = seq[left]
close2 = seq[right]
close3 = seq[x]

the above statements will check closest from the previous set and current set of left, right and x elements of array, and change the close1, close2 and close2 to current set of left, right and x if current combination is closer than the previous record of left, right and x which is stored in close1, close2 and close3 respectively.Otherwise close1, close2 and close3 shall not be changed. and at the end of code 

#if no match is found,return the closest set
return [close1 ,close2, close3]
Akhil
  • 105
  • 1
  • 8