Hi all, my school-time is some decades back and i really would appreciate if someone could help with my problem i have to solve:
I have an array (no. of elements is variing, max. is about 150) with different values and a result.
I have to check all array-elements in any combination so the addition of a combination is = result.
The output has to give out all combinations.
Does someone have some code to share or a link where to look?
thx
The first step is to describe a solution, before you can code it. Here’s a Wikipedia article that describes the problem.
You can find several algorithms via google. The next step would be to choose an approach and write xojo code for it. We can help you if you get stuck with that.
Rolf, if I understood correctly your problem, I think a matrix should help to solve it.
Dim I, J as integer
Dim Total As Integer
Dim numbers() As Integer
numbers = Array(1,5, 13,17,8,9,19,11,7,15)
Total = 20
For I = 0 to UBound(numbers) - 1
For J = I + 1 to UBound(numbers)
If numbers(I) + numbers(J) = Total Then
// elements found
msgbox(str(numbers(I)) + " + " + str(numbers(J)) + " = " + str(total))
End If
Next
Next
The problem with that code is that it will only check for a combination of 2 elements. In your example, though, 1 + 8 + 11 will reach the Total too.
Thanks for the answers so far.
@Tim I’ve read these articles and hoped someone may already have some smart code for that since I think this task occures more often. The code I found until now isn’t readable for me (i don’t have a clue about C/Java etc.) and does not seem to solve this particular problem.
I took a shot and came up with this:
Function ElementsWithSum(arr() As Integer, total As Integer) As Dictionary
dim result as new Dictionary
if arr.Ubound = -1 then return result
dim sortedArr() as Integer = CloneArray( arr )
sortedArr.Sort
dim set() as Integer
call ElementsWithSumRecursive( sortedArr(), total, 0, set(), 0, result )
return result
End Function
Private Function ElementsWithSumRecursive(origArr() As Integer, total As Integer, arrIndex As Integer, set() As Integer, setSum As Integer, result As Dictionary) As Boolean
// This function will return True unless the set sum is pushed past total
// by the next array element.
dim r as Boolean = False
dim thisElement as Integer = origArr( arrIndex )
dim newSetSum as Integer = setSum + thisElement
if newSetSum > total then
r = False
elseif newSetSum = total then
dim clone() as Integer = CloneArray( set )
clone.Append thisElement
result.Value( result.Count ) = clone
r = True
else // newSetSum < total
set.Append thisElement
arrIndex = arrIndex + 1
for i as Integer = arrIndex to origArr.Ubound
if not ElementsWithSumRecursive( origArr(), total, i, set(), newSetSum, result ) then
exit // No point in checking the rest
end if
next i
call set.Pop
r = True
end if
return r
End Function
Private Function CloneArray(arr() As Integer) As Integer()
dim clone() as Integer
redim clone( arr.Ubound )
for i as Integer = 0 to arr.Ubound
clone( i ) = arr( i )
next i
return clone
End FunctionEach value of the Dictionary will be an Integer array.
A bit of an optimization here. If a chain of elements never reaches the total, there is no point in continuing to check that line.
Private Function ElementsWithSumRecursive(origArr() As Integer, total As Integer, arrIndex As Integer, set() As Integer, setSum As Integer, result As Dictionary) As Integer
// The result will be
// -2 none of the remaining elements in the array ever reached the total
// -1 adding the next element was < total but subsequent values reached or exceeded it
// 0 adding the next element = total
// 1 adding the next element > total
dim r as Integer = -1
dim thisElement as Integer = origArr( arrIndex )
dim newSetSum as Integer = setSum + thisElement
if newSetSum > total then
r = 1
elseif newSetSum = total then
dim clone() as Integer = CloneArray( set )
clone.Append thisElement
result.Value( result.Count ) = clone
r = 0
else // newSetSum < total
set.Append thisElement
arrIndex = arrIndex + 1
dim neverExceeded as Boolean = True
for i as Integer = arrIndex to origArr.Ubound
dim nextLevel as Integer = ElementsWithSumRecursive( origArr(), total, i, set(), newSetSum, result )
if nextLevel = 1 then
neverExceeded = False
r = -1
exit // No point in checking the rest
elseif nextLevel = 0 then
neverExceeded = False // But keep checking
r = -1
elseif nextLevel = -2 then
r = -2
exit
end if
next i
call set.Pop
if neverExceeded then
r = -2
end if
end if
return r
End FunctionAlso, you may have to run this in a Thread to control the stack size.
Woha. Thank you Kem! Can’t wait to get home and try your code.
Played a little with the code provided from Tim. Nice.
If I see it right I have to build Arrays of all possible combinations (2^n) and then test them with the code provided above, correct?
If you meant my code, and you meant that you should create unit tests to confirm, then yes.
Meanwhile, I found a bug. My code only starts with the first element, but the recursive code has to be called with each index of the array in turn.
Function ElementsWithSum(arr() As Integer, total As Integer) As Dictionary
dim result as new Dictionary
if arr.Ubound = -1 then return result
dim sortedArr() as Integer = CloneArray( arr )
sortedArr.Sort
dim set() as Integer
for index as Integer = 0 to sortedArr.Ubound
select case ElementsWithSumRecursive( sortedArr(), total, index, set(), 0, result )
case -2, 1
exit // Never reached total or exceeded total
end select
next index
return result
End FunctionI also had to move this into a thread to prevent a stack overflow. If I have time, I’ll see if I can rework this to use a stack rather than recursion.
Well, this keeps snowballing. You MUST limit your results or you will exceed memory. For example, if you have an array of the integers 1 thru 150 and you look for combinations that reach a total of 150, you will crash because of the sheer number of combinations.
Kem, sure I meant your code, sorry.
I figured already that only the first element was tested and modified the code almost like you did.
And I had that snowball, too.
Recursing functions always give me a headache. But this one is challenging to me.
If I come up with something useful I’ll post it; further help always welcome 
You must set a limit or figure out a different way to report your results (maybe write them to a file or as a string?). The problem isn’t in the recursion which can only go 150 levels deep at most. The problem is the sheer number of results found. The number of arrays swamps memory.
FYI, I was able to get to 10 million results without crashing. I didn’t test further than that, and I don’t know what the practical use of such a result would be.
Oh my, sorry Kem, I wrote something incomlete:
I have to get all combinations that match a defined result. I did not write that in the first message. Darn.
To make a practical real world example (it’s not what I have in mind but this is similar):
Let’s say a client has about 100 bills to pay. He wired amount x, What bills did he have paid for?
And an new addition to it: To make things worse bills could be paid twice or more.
I tried that with a simple “try everything” permutation-routine (that worked in reasonable time only if less then 6 elements), but as I wrote I still can’t figure out how to accomplish this task.
Maybe because of a huge deficit on sleep, or I’m simply too dumb, or both.
Anyway, many thanks for your effort! I’ll give it another try next weekend.
I’m pretty sure you did write that. How does your recent description differ?
FYI, I reworked my test code just to get a count without actually storing the results. It turns out that, with an array of integers starting at 1 through 150 consecutive, the number of combinations that add up to 150 are
19,406,016.
I checked my code to make sure there were no duplicates among the results, and there weren’t. Would you have guessed that? I wouldn’t have.
It took about 3.25 minutes to find and report all of those results.