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.

Improve this question
0

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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
That's great, enjoy!
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
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]
Improve this answer

Comments

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.