Find sum in a list

[if1467]

I am using VB in excel and I have a list of numbers in column A and I am trying to find which numbers match up to make a sum of another number. The list of numbers is quite lengthy, and there may be more then one combination.

Ex.

List = 1 2 3 4 5 6
Sum = 10
output = 1,2,3,4 and 1,3,6 and 1,4,5 and 2,3,5 and 4,6

Any ideas?

[kadghar]

I am using VB in excel and I have a list of numbers in column A and I am trying to find which numbers match up to make a sum of another number. The list of numbers is quite lengthy, and there may be more then one combination.

Ex.

List = 1 2 3 4 5 6
Sum = 10
output = 1,2,3,4 and 1,3,6 and 1,4,5 and 2,3,5 and 4,6

Any ideas?

Its not as easy as you think. A not very hard way (but not very efficient) will be creating all the posibles combinations: 2^n, and check the ones that satisfy the sum.
i'd make a matrix of 2^n x 2, where for each combination, we'll have the combination and its sum, then check sum by sum if it matches with your number.
e.g.
list: 1, 2, 3
sum = 3

the matrix will be of 2^3 = 8 x 2 (actually 7x2, because we'll not consider the empty one)
the matrix will look like his:

combination     sum
  1               1
  2               2
  3               3
  1,2             3
  1,3             4
  2,3             5
  1,2,3           6

and the entrances it'll return will be 3 and 1,2.

With some recursivity, it can be done.

HTH

[Killer42]

It's a very interesting problem, and one which I feel should be directed toward any mathematicians present. It's really not a VB-specific question, but one of deriving an algorithm to handle the situation. Given the algorithm we can easily (probably) translate to VB.

Kadghar, I think that if anything, you've underestimated the number of possible combinations.


EDIT: I've dropped a post into the Software Development forum asking anyone interested to have a look here.

[kadghar]

...
Kadghar, I think that if anything, you've underestimated the number of possible combinations.
...

Sounds like a challenge to me!!
^.^

Well, since its late at night, i wont make the best algorithm, but this one will work if the list has less than 170 numbers (because a double wont allow any factorial over 170, and im using combinations)

This is made for Excel's VBA, it'll read the list from column A (there shouldnt be blank spaces) and reads the sum from cell B1.

It wont work if any value of the list is repeated, and it wont show the obvious solution (i.e.it wont show the solutions of only one number, only combinations of 2 or more members of the list)

[CODE=vb]Sub FindCombination s()
Dim a, Var1
Dim b()
Dim Result() As String, Result2() As String
Dim Dou1 As Double
Dim i As Integer
a = Range(Cells(1, 1), Cells(1, 1).End(-4121))
Dou1 = Cells(1, 2)
ReDim b(1 To UBound(a) - 1)
b(1) = TwoNums(a, a)
For i = 2 To UBound(b)
b(i) = nNums(b, a, i)
Next
ReDim Result(1 To 1)
For Each Var1 In b
For i = 1 To UBound(Var1)
If Var1(i, 2) = Dou1 Then
ReDim Preserve Result(1 To UBound(Result) + 1)
Result(UBound(R esult)) = Var1(i, 1)
End If
Next
Next
ReDim Result2(1 To UBound(Result) - 1, 1 To 1)
For i = 2 To UBound(Result)
Result2(i - 1, 1) = Result(i)
Next
Range(Cells(1, 3), Cells(UBound(Re sult) - 1, 3)) = Result2
End Sub
Function TwoNums(Arr1, Arr2)
Dim i As Long: Dim j As Long: Dim k As Long
Dim Arr3() As String
'array with 2 nums
ReDim Arr3(1 To Combinations(UB ound(Arr1), 2), 1 To 2)
For i = 1 To UBound(Arr1)
If Mid$(Arr1(i, 1), InStrRev(Arr1(i , 1), ",") + 1) <> Arr2(UBound(Arr 2), 1) Then
For j = i + 1 To UBound(Arr2)
k = k + 1
Arr3(k, 1) = Arr1(i, 1) & "," & Arr2(j, 1)
Arr3(k, 2) = Val(Arr1(i, 1) + Arr2(j, 1))
Next
End If
Next
TwoNums = Arr3
End Function
Function nNums(Arr1, Arr2, n As Integer)
Dim i As Long: Dim j As Long: Dim k As Long
Dim Boo1 As Boolean
Dim Arr3() As String
ReDim Arr3(1 To Combinations(UB ound(Arr2), n + 1), 1 To 2)
For i = 1 To UBound(Arr1(n - 1))
Boo1 = False
For j = 1 To UBound(Arr2)
If Boo1 = True Then
k = k + 1
Arr3(k, 1) = Arr1(n - 1)(i, 1) & "," & Arr2(j, 1)
Arr3(k, 2) = CDbl(Val(Arr1(n - 1)(i, 2)) + Val(Arr2(j, 1)))
End If
If Mid$(Arr1(n - 1)(i, 1), InStrRev(Arr1(n - 1)(i, 1), ",") + 1) = Arr2(j, 1) Then Boo1 = True
Next
Next
nNums = Arr3
End Function

Function Factorial(ByVal i As Integer) As Double
Factorial = 1
While i > 1
Factorial = Factorial * i
i = i - 1
Wend
End Function
Function Combinations(n As Integer, k As Integer) As Double
Combinations = Factorial(n) / (Factorial(k) * Factorial(n - k))
End Function[/CODE]

^.^ wasnt that hard (anyway, it can be improved, this one is not efficient)

[if1467]

Sounds like a challenge to me!!
^.^

Well, since its late at night, i wont make the best algorithm, but this one will work if the list has less than 170 numbers (because a double wont allow any factorial over 170, and im using combinations)

This is made for Excel's VBA, it'll read the list from column A (there shouldnt be blank spaces) and reads the sum from cell B1.

It wont work if any value of the list is repeated, and it wont show the obvious solution (i.e.it wont show the solutions of only one number, only combinations of 2 or more members of the list)

^.^ wasnt that hard (anyway, it can be improved, this one is not efficient)

So I tried this on the actual numbers I have (did i forget to mention that there are 49 in this particuliar set) and my computer returned "Do I look like I cost more than $1,500?".

So.....any more efficient ideas would be greatly appreciated or a donation to my supercomputer fund.

kadghar - thanks for your effort, it works great on small sets of numbers!!

[kadghar]

So I tried this on the actual numbers I have (did i forget to mention that there are 49 in this particuliar set) and my computer returned "Do I look like I cost more than $1,500?".

So.....any more efficient ideas would be greatly appreciated or a donation to my supercomputer fund.

kadghar - thanks for your effort, it works great on small sets of numbers!!

Are you aware that you have 2^49 - 1 = 562'949'953'421 '311 possible combinations?
And with my awesome deductive power, i'd say you computer didnt cost over $1,500.
To evaluate an IF/THEN should take it about 1 / 10^7 seconds. So... assuming you already have all the posible combinations and their values. And you only want to check if its value is the same as the SUM. That'll take 56'294'995 seconds.
That is 1 year, 9months, 16 days (aprox).

But, since you dont have all the combinations yet, neither their values, i'd say that in 50, may be 60 years you'll get your result.

The only thing that comes to my mind now is... in order to make this somehow faster, i'll recomend you to sort the list, then take the biggest number, smaller than the SUM, and check number by number, if it wont make your tmpResult exceed the SUM take it, once you find a good combination, start with some other number, and so on... many times.. This way you wont get all the possible combinations, but you can control how many results you want. May be the first 10 are good enough for what you need.

[kadghar]

oh, i forgot..
may be another solution will be, for 49 numbers, there are
1176 combinations of 2 numbers
18424 of 3
211876 of 4
1906884 of 5
13983816 of 6

this means that if you only want the possible combinations with 6 or less numbers, we're talking of 16'122'176 combinations. I think this will take only a few minutes, and the result might be helpful

Actually, if you want the combinations of 10 numbers or less, they are 10'825'278'996. Im sure you can get them in 3 or 4 hours.

Note:
To do this just change line 9
ReDim b(1 To n-1)
e.g ReDim b(1 to 9) will do for up to 10 ^.^

[if1467]

oh, i forgot..
may be another solution will be, for 49 numbers, there are
1176 combinations of 2 numbers
18424 of 3
211876 of 4
1906884 of 5
13983816 of 6

this means that if you only want the possible combinations with 6 or less numbers, we're talking of 16'122'176 combinations. I think this will take only a few minutes, and the result might be helpful

Actually, if you want the combinations of 10 numbers or less, they are 10'825'278'996. Im sure you can get them in 3 or 4 hours.

Note:
To do this just change line 9
ReDim b(1 To n-1)
e.g ReDim b(1 to 9) will do for up to 10 ^.^

What if I wanted to put a limit on the number of outputs. For example, take the first 5 combinations that work, or even better only take the first combination. Do you think that would help, and how would I modify your code to do this?

[kadghar]

What if I wanted to put a limit on the number of outputs. For example, take the first 5 combinations that work, or even better only take the first combination. Do you think that would help, and how would I modify your code to do this?

yes, that might help, but you'll have to make a different code.

this code, first get all the combinations and its sum, then checks every sum. It uses some kind of recursivity to create the combinations of each size (it starts with size 2, then 3, and so on)
What you can do for sure, is to make it do all combinations for 2 and 3

redim b(1 to 2)

it wont take more than 5 seconds, and hopefully, you'll get more than some answers.

HTH

[kadghar]

i made a little test.
i fill the A column with numbers from 1 to 49

then i asked for the 2, 3 and 4 number combinations that sum 98 (well, there will be only of 3 and 4, since 49+48 = 97).

It took less than 10 seconds to show me there are 3'172 posible ways to sum 98 using 3 or 4 numbers from 1 to 49. Thats a nice result.

Oh, please note i made a mistake, i declared some integers, change them to longs, or even better, to doubles (you shouldnt have any problem by doing this).

[Killer42]

Sounds like a challenge to me!!

Thanks for all your input here Kadghar. It's obvious how much you hated doing all that hard work. ;)

Was I right about the number of combinations?

[kadghar]

Thanks for all your input here Kadghar. It's obvious how much you hated doing all that hard work. ;)

What can i say? I enjoy my work.

Was I right about the number of combinations?

I was expecting 15 or 20 numbers.

but 49!! that's insane!! It's like the Chess Board tale.

[Killer42]

...but 49!! that's insane!! It's like the Chess Board tale.

Is that the one about doubling the number of grains of rice?

[kadghar]

Is that the one about doubling the number of grains of rice?

Yes, in that one, the last square would have 2^63 grains
But 2^49 stills a crazy number.

[Killer42]

Yes, in that one, the last square would have 2^63 grains
But 2^49 stills a crazy number.

Hahaha... I remember when I read that, the final amount was something like 13 trillion tons of rice. :D