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?
18 7240
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
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, 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) - Sub FindCombinations()
-
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(Result)) = 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(Result) - 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(UBound(Arr1), 2), 1 To 2)
-
For i = 1 To UBound(Arr1)
-
If Mid$(Arr1(i, 1), InStrRev(Arr1(i, 1), ",") + 1) <> Arr2(UBound(Arr2), 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(UBound(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
^.^ wasnt that hard (anyway, it can be improved, this one is not efficient)
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!!
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.
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 ^.^
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?
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
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).
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?
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.
...but 49!! that's insane!! It's like the Chess Board tale.
Is that the one about doubling the number of grains of rice?
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.
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
Just to the interested ones, I left a solution in the Software Development forum.
kind regards,
Jos
Just to the interested ones, I left a solution in the Software Development forum.
How about a link?
How about a link?
Lazy bones ... here.
kind regards,
Jos
Lazy bones ...
It wasn't for me.
:P
Sign in to post your reply or Sign up for a free account.
Similar topics
by: Greg Yasko |
last post by:
Hi. Does anyone know if there's an equivalent of Perl's file::find
module in Python? It traverses a directory. I've googled extensively and
checked this newsgroup and can't find anything like it...
|
by: Poewood |
last post by:
Okay here are four classes for a pocket pc program: Input, fpositional,
ComboBoxArray and TextBoxArray. The "input" class is the form. I use the
fpositional class to handle most of the functions...
|
by: Jeff User |
last post by:
Hi
C# .NET1.1
I have read Visual Studio help and several articles on the web.
Obviously this is a common topic. However, I see this code over and
over yet I am stuck with the FindControl method...
|
by: KL |
last post by:
Hello again,
I am still working on this homework assignment and have hit a wall.
I have a list that I want to fill with all occurences of img tags from a
big string of html code. So I have a...
|
by: micklee74 |
last post by:
hi
say i have string like this
astring = 'abcd efgd 1234 fsdf gfds abcde 1234'
if i want to find which postion is 1234, how can i achieve this...? i
want to use index() but it only give me the...
|
by: andrewcw |
last post by:
I looked at this code on MSDN ( and at article in MSDN magazine this month ):
The code below suggests that I may be able to use the find function of
generics to locate the object easily as opposed...
|
by: OppThumb |
last post by:
Hi,
I've been searching this newsgroup for an answer to my question, and
the closest I've come asks my question, but in reverse ("How to figure
out the program from plan/package"). I've -- shall...
|
by: Satish Itty |
last post by:
How do I write the following c# code in vb
Product FindProduct(string code)
{
List<Productproducts = getProducts();
return products.Find(delegate(Product bo)
{ return bo.Code == code; });
}
|
by: Steve Richter |
last post by:
Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?
ex:...
|
by: =?Utf-8?B?V2ViQnVpbGRlcjQ1MQ==?= |
last post by:
i have a master page and aseries of controls labeled fn1, fn2, fn3 , ...
i want ot loop and use find control but i'm finding them.
i'm using the following w/o luck
ContentPlaceHolder cph =...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |