Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
From a set of integers from 1 to 49,
take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, |
#2
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
In the past I've posted code to generate combinations. You can find it by searching Google for
posts from Myrna Larson, key words "combinations" "permutations". The message you want was posted on July 25, 2000. There are almost 14 million combinations of 49 items taken 6 at a time, so the code will take a while to run (maybe hours?) There will be 214 columns of text. You'll need to split the data from 1 column into 6 (data/text to columns) plus a 7th column for a SUM formula, so you'll need 1498 columns, which means 6 worksheets with data from ~36 columns on each. Once you've generated the combinations, copied to multiple sheets, split into 6 numbers and done the SUMs, you can use Data/AutoFilter to show the total you want. I hope Excel won't choke on this amount of data. It will undoubtedly be VERY SLOW! I presume this has something to do with the lottery? Whatever your scheme, it won't work <g. On Mon, 08 Sep 2003 04:29:30 GMT, TwIsTeEeR wrote: From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, |
#3
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
Hi Myrna,
My question has not to do with the lottery, but I used the values of a lottery game to attract some attention. I'm asking only of the quantity of such combinations on my first question. * How many such combinations exist? I imagine your function is of a brute force nature. I'm not looking for somthing like that. I'm looking for an equation. On my second question. * Does a genetrating function exist to satisfy different values? Thank you, Myrna Larson wrote: In the past I've posted code to generate combinations. You can find it by searching Google for posts from Myrna Larson, key words "combinations" "permutations". The message you want was posted on July 25, 2000. There are almost 14 million combinations of 49 items taken 6 at a time, so the code will take a while to run (maybe hours?) There will be 214 columns of text. You'll need to split the data from 1 column into 6 (data/text to columns) plus a 7th column for a SUM formula, so you'll need 1498 columns, which means 6 worksheets with data from ~36 columns on each. Once you've generated the combinations, copied to multiple sheets, split into 6 numbers and done the SUMs, you can use Data/AutoFilter to show the total you want. I hope Excel won't choke on this amount of data. It will undoubtedly be VERY SLOW! I presume this has something to do with the lottery? Whatever your scheme, it won't work <g. On Mon, 08 Sep 2003 04:29:30 GMT, TwIsTeEeR wrote: From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, |
#4
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
As I understood Myrna, the nearly 14 million combinations
are the total possible for 6 elements from a list of 49. (See the worksheet function Combin). This is not the limited set that sum to 150. You can obtain the number of combinations of 6 values that sum to 150 using nested For/Next loops (i.e. brute force as you put it). As you are aware, this would normally take a very long time. However, in this case, since the numbers 1 to 49 are in ascending order, you can include code that aborts each loop once the sum exceeds 150 since there would no longer be any point in continuing (because the sum can only get bigger). This should drastically reduce the time, I would think, but will still likely be quite long. The code to abort the inner loop is simple but a bit tricky for the remainder. I'm pretty sure I've got it figured out however. If your're interested, I could give it a whirl. My guess is that the number will be in excess of 100,000 !!! Regards, Greg -----Original Message----- From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, . |
#5
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
TwIsTeEeR wrote:
From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, A mathematical answer came from: The coefficient of s^6 t^150 in (1+st)(1+st^2)...(1+st^49). Let P_0 = 1, and for j = 1 to 49 let P_j = P_{j-1} (1+st^j) mod <s^7, t^151 (i.e. multiply it out and remove any term involving s^i with i =7 or t^k with k = 151). In Maple you can do it with P[0]:= 1; for j from 1 to 49 do P[j]:= rem(rem(P[j-1]*(1+s*t^j),s7,s),t151,t) od: coeff(coeff(P[49],t,150),s,6); 165772 A somewhat more prosaic dynamic-programming solution is also possible, and would have faster execution time, but would require more time to program. Robert Israel Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 Is it posible to create a VBA function to satisfy the second question, using the above answer? |
#6
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
TwIsTeEeR wrote:
From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, The code below satisfies the first part of the question. Is it possible to convert this code to a recursive function, so that the term SetSize can be satisfied also? Thanks, Sub Test() Dim minval As Integer Dim maxval As Integer Dim Target As Long Dim sum As Long Dim Cnt As Long Dim SetSize As Integer Dim RetVals As String minval = 1 maxval = 49 SetSize = 6 Target = 150 sum = 0 For I = minval To (Target + 5) / 6 - 3 sum = sum + I For J = I + 1 To (Target + 4 - sum) / 5 - 2 sum = sum + J For K = J + 1 To (Target + 3 - sum) / 4 - 2 sum = sum + K For L = K + 1 To (Target + 2 - sum) / 3 - 1 sum = sum + L For M = L + 1 To (Target + 1 - sum) / 2 - 1 N = Target - sum - M If (N <= maxval) Then Cnt = Cnt + 1 End If Next sum = sum - L Next sum = sum - K Next sum = sum - J Next sum = sum - I Next RetVals = MsgBox("When " & vbTab & "MinN=" & minval & _ vbNewLine & " " & vbTab & "MaxN=" & maxval & _ vbNewLine & " " & vbTab & "Set size=" & SetSize & _ vbNewLine & " " & vbTab & "Sum=" & Target & vbNewLine & _ "There are = " & Cnt & " Combinations to satisfy the condition." & vbNewLine & " ", 64, "Combinations...") Select Case RetVals Case 1: 'OK End Select End Sub |
#7
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
Be advised that I don't get the same result using your
macro as I do mine. My macro is appended. I recommend that you double check your macro although I won't say with 100% certainty that mine is the correct one. In order to check mine, I inserted some 'demo code' into the macro. This allowed me to monitor what was being referenced by the For/Next loops. For the demo, the row numbers represented the values being summed. My conclusion was that the code works as advertised. Note that all loops are aborted once the sum = 150. This can get confusing when more than one abort at the same time. If you run the demo you should reduce all references to 150 to, say, 50 instead to save time. Also, you need to enable the screen updating. Public Declare Sub Sleep Lib "kernel32.dll" (ByVal dwMilliseconds As Long) Sub Combinations() Dim a As Integer, b As Integer, c As Integer Dim d As Integer, e As Integer, f As Integer Dim Results As Long 'Application.ScreenUpdating = False Results = 0 For a = 1 To 49 If a + b + c + d + e + f = 150 Then Exit For For b = a + 1 To 49 If a + b + c + d + e + f = 150 Then b = a + 2: c = b + 1: d = c + 1: e = d + 1: f = e + 1 Exit For End If For c = b + 1 To 49 If a + b + c + d + e + f = 150 Then c = b + 2: d = c + 1: e = d + 1: f = e + 1 Exit For End If For d = c + 1 To 49 If a + b + c + d + e + f = 150 Then d = c + 2: e = d + 1: f = e + 1 Exit For End If For e = d + 1 To 49 If a + b + c + d + e + f = 150 Then e = d + 2: f = e + 1 Exit For End If For f = e + 1 To 49 Cells(a, 1).Interior.ColorIndex = 6 'Demo code Cells(b, 2).Interior.ColorIndex = 6 'Demo code Cells(c, 3).Interior.ColorIndex = 6 'Demo code Cells(d, 4).Interior.ColorIndex = 6 'Demo code Cells(e, 5).Interior.ColorIndex = 6 'Demo code Cells(f, 6).Interior.ColorIndex = 6 'Demo code Range("H1") = a + b + c + d + e + f 'Demo code Sleep 300 'Demo code Range("A1:F49").Interior.ColorIndex = xlNone 'Demo code If a + b + c + d + e + f = 150 Then Results = Results + 1 Range("I1") = Results 'Demo code f = e + 2 Exit For End If Next f Next e Next d Next c Next b Next a Application.ScreenUpdating = True MsgBox "The number of combinations that sum to 150 a " & _ Results & " ", vbInformation, "Combinations" End Sub Regards, Greg -----Original Message----- TwIsTeEeR wrote: From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, The code below satisfies the first part of the question. Is it possible to convert this code to a recursive function, so that the term SetSize can be satisfied also? Thanks, Sub Test() Dim minval As Integer Dim maxval As Integer Dim Target As Long Dim sum As Long Dim Cnt As Long Dim SetSize As Integer Dim RetVals As String minval = 1 maxval = 49 SetSize = 6 Target = 150 sum = 0 For I = minval To (Target + 5) / 6 - 3 sum = sum + I For J = I + 1 To (Target + 4 - sum) / 5 - 2 sum = sum + J For K = J + 1 To (Target + 3 - sum) / 4 - 2 sum = sum + K For L = K + 1 To (Target + 2 - sum) / 3 - 1 sum = sum + L For M = L + 1 To (Target + 1 - sum) / 2 - 1 N = Target - sum - M If (N <= maxval) Then Cnt = Cnt + 1 End If Next sum = sum - L Next sum = sum - K Next sum = sum - J Next sum = sum - I Next RetVals = MsgBox("When " & vbTab & "MinN=" & minval & _ vbNewLine & " " & vbTab & "MaxN=" & maxval & _ vbNewLine & " " & vbTab & "Set size=" & SetSize & _ vbNewLine & " " & vbTab & "Sum=" & Target & vbNewLine & _ "There are = " & Cnt & " Combinations to satisfy the condition." & vbNewLine & " ", 64, "Combinations...") Select Case RetVals Case 1: 'OK End Select End Sub . |
#8
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
There exists a better code. It is in java that I'm not familiar with. http://www.btinternet.com/~se16/js/partitions.htm with Partitions with distinct terms of: 150 Exact number of terms: 6 Each term no more than: 49 and then look at the Java code http://www.btinternet.com/~se16/js/PartitionChoice.java Myrna Larson wrote: I modified my recursive code which generates all possible combinations so it sums the 6 numbers and increments a counter if the total is 150 (rather than writing the sets to the worksheet). With the numbers 1-49, set size 6, I got 165,722 combinations that total 150. It took about 20 seconds on my machine (2.8 gHz P4, 1.5 gB memory). This is without any attempt to abort the recursion when the total is 150. I'm sure that recursion will be slower here (having to set up and tear down 6 stack frames for each combination) than 6 nested For/Next loops, but that's the price of flexibility in the set size. On Tue, 9 Sep 2003 00:09:14 -0700, "Greg Wilson" wrote: Be advised that I don't get the same result using your macro as I do mine. My macro is appended. I recommend that you double check your macro although I won't say with 100% certainty that mine is the correct one. In order to check mine, I inserted some 'demo code' into the macro. This allowed me to monitor what was being referenced by the For/Next loops. For the demo, the row numbers represented the values being summed. My conclusion was that the code works as advertised. Note that all loops are aborted once the sum = 150. This can get confusing when more than one abort at the same time. If you run the demo you should reduce all references to 150 to, say, 50 instead to save time. Also, you need to enable the screen updating. Public Declare Sub Sleep Lib "kernel32.dll" (ByVal dwMilliseconds As Long) Sub Combinations() Dim a As Integer, b As Integer, c As Integer Dim d As Integer, e As Integer, f As Integer Dim Results As Long 'Application.ScreenUpdating = False Results = 0 For a = 1 To 49 If a + b + c + d + e + f = 150 Then Exit For For b = a + 1 To 49 If a + b + c + d + e + f = 150 Then b = a + 2: c = b + 1: d = c + 1: e = d + 1: f = e + 1 Exit For End If For c = b + 1 To 49 If a + b + c + d + e + f = 150 Then c = b + 2: d = c + 1: e = d + 1: f = e + 1 Exit For End If For d = c + 1 To 49 If a + b + c + d + e + f = 150 Then d = c + 2: e = d + 1: f = e + 1 Exit For End If For e = d + 1 To 49 If a + b + c + d + e + f = 150 Then e = d + 2: f = e + 1 Exit For End If For f = e + 1 To 49 Cells(a, 1).Interior.ColorIndex = 6 'Demo code Cells(b, 2).Interior.ColorIndex = 6 'Demo code Cells(c, 3).Interior.ColorIndex = 6 'Demo code Cells(d, 4).Interior.ColorIndex = 6 'Demo code Cells(e, 5).Interior.ColorIndex = 6 'Demo code Cells(f, 6).Interior.ColorIndex = 6 'Demo code Range("H1") = a + b + c + d + e + f 'Demo code Sleep 300 'Demo code Range("A1:F49").Interior.ColorIndex = xlNone 'Demo code If a + b + c + d + e + f = 150 Then Results = Results + 1 Range("I1") = Results 'Demo code f = e + 2 Exit For End If Next f Next e Next d Next c Next b Next a Application.ScreenUpdating = True MsgBox "The number of combinations that sum to 150 a " & _ Results & " ", vbInformation, "Combinations" End Sub Regards, Greg -----Original Message----- TwIsTeEeR wrote: From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, The code below satisfies the first part of the question. Is it possible to convert this code to a recursive function, so that the term SetSize can be satisfied also? Thanks, Sub Test() Dim minval As Integer Dim maxval As Integer Dim Target As Long Dim sum As Long Dim Cnt As Long Dim SetSize As Integer Dim RetVals As String minval = 1 maxval = 49 SetSize = 6 Target = 150 sum = 0 For I = minval To (Target + 5) / 6 - 3 sum = sum + I For J = I + 1 To (Target + 4 - sum) / 5 - 2 sum = sum + J For K = J + 1 To (Target + 3 - sum) / 4 - 2 sum = sum + K For L = K + 1 To (Target + 2 - sum) / 3 - 1 sum = sum + L For M = L + 1 To (Target + 1 - sum) / 2 - 1 N = Target - sum - M If (N <= maxval) Then Cnt = Cnt + 1 End If Next sum = sum - L Next sum = sum - K Next sum = sum - J Next sum = sum - I Next RetVals = MsgBox("When " & vbTab & "MinN=" & minval & _ vbNewLine & " " & vbTab & "MaxN=" & maxval & _ vbNewLine & " " & vbTab & "Set size=" & SetSize & _ vbNewLine & " " & vbTab & "Sum=" & Target & vbNewLine & _ "There are = " & Cnt & " Combinations to satisfy the condition." & vbNewLine & " ", 64, "Combinations...") Select Case RetVals Case 1: 'OK End Select End Sub . |
#9
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
Be my guest! You can't write Excel macros in Java. You'll have to do it with
a free-standing app. Good luck. "TwIsTeR" wrote in message ble.rogers.com... There exists a better code. It is in java that I'm not familiar with. |
#10
Posted to microsoft.public.excel.programming
|
|||
|
|||
Count combinations
I didn't conclude that he wanted the most frequent total. I thought he
wanted to be able to vary all 3 parameters -- number range, size of set, and desired total. But you may be correct. "Dana DeLouis" wrote in message ... I don't have an answer, just an observation... With the range of numbers 1-10 (Instead of 1-49), and you take all combinations of 6: The smallest combination total is 21 (1,2,3,4,5,6), and occurs only once. The Largest combination total 45 {5, 6, 7, 8, 9, 10}, and also occurs once. The average of these two numbers (21+45)/2 is the number that occurs the most often. The answer here is 33. In a range of 10 numbers taken 6 at a time, a total of 33 occurs the most. If the Range is 1-49, taken 6 at a time, the total that occurs the most often is: (21 + 279)/2 150 It appears the op is asking about the total count of the sum that occurs the most often. The brute force method generates many combinations. Instead, I looked at the total of combinations from a smaller range of numbers. First, Range 1-6, and made permutations of 6 (basically just one solution) then Range 1-7, Range 1-8, etc I did this quickly for the range 1-(6-20) The number that occurs the most (when grouped as 6 numbers) generated the following sequence. {1, 1, 4, 8, 18, 32, 58, 94, 151, 227, 338, 480, 676, 920, 1242, 1636} Apparently, this is a know integer sequence (A001977). The bad news is that it does not give the generating function directly. It is listed as a form of "Restricted partitions." http://www.research.att.com/cgi-bin/...i?Anum=A001977 Maybe someone with more knowledge can shed some light on this. I have never seen a result listed like this before, so this would be new to me. Harlan? Tushar? The program Mathematica has the function PartitionsP, which I am sure your Maple program does also: Information[PartitionsP] "PartitionsP[n] gives the number p(n) of unrestricted partitions of the integer n." Attributes[PartitionsP] = {Listable, Protected} Here are the first few terms... Table[PartitionsP[n], {n, 0, 15}] {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176} It looks like this function fits in somewhere, but I do not know enough about it. I don't see any pattern. Harlan? Tushar? -- Dana DeLouis Using Windows XP & Office XP = = = = = = = = = = = = = = = = = "TwIsTeEeR" wrote in message able.rogers.com... From a set of integers from 1 to 49, take 6 unique integers, that if we sum them up, this sum is equal to 150. Conditions: 1. The set numbers are integers from 1 to 49 2. subset size is 6 3. sum of the selected subset numbers is 150 My questions: A. How many sets (combinations) of 6 unique numbers exist that their sum is 150? B. Do you know of a function that can calculate that quantity of combinations, for different values of conditions (1), (2), & (3)? Thank you, |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
combinations | Excel Discussion (Misc queries) | |||
Sum of combinations | Excel Discussion (Misc queries) | |||
Possible Combinations | Excel Discussion (Misc queries) | |||
Combinations | Excel Worksheet Functions | |||
count combinations | Excel Discussion (Misc queries) |