Programming Challange:

[NotLKH]

Alright! I'd like to see all of you do your best in the following:

Given a Matrix of the numbers 1 thru 61

and, given a target array of 6 elements:


Build an app that generates every combination of 61 elements from 1 thru 61, taken 6 at a time that add to 150, and counts how many total it generates. When its done, it msgbox'es the count.

It must be generic enough so that we can vary the target sum, the number of elements in the source array, and the number of elements in the target array.

Any Questions?

Private Sub cmdAddsTo2_Click()
    Dim MyStartTick As Long
    Dim MyEndTick As Long
    Dim MyI As Integer
    Dim MyCounter As Long
'Lets do 61 elements
    Dim MySourceArr() As Integer
    ReDim MySourceArr(60)
    For MyI = 0 To 60
        MySourceArr(MyI) = MyI + 1
    Next MyI
'taken 6 at a time
    Dim My4_arr() As Integer
    ReDim My4_arr(5)
'that adds to 150
    Dim ItAddsTo As Long
    ItAddsTo = 150
    MyCounter = 0
    MyStartTick = GetTickCount
    Call YOUR_SUB_OR_FUNCTION_HERE(MySourceArr,  My4_arr, MyCounter, _
        ItAddsTo, ...[i]anything else you need[/i])
    MyEndTick = GetTickCount
    MsgBox MyCounter & " Took " & (MyEndTick - MyStartTick) / 1000
End Sub

for example, an outline view of my sub looks like the folowing:

Private Sub NUM_SUM_COMBS_2(ByRef IN_Arr() As Integer, _
        ByRef HowDeep As Integer, ByVal MyLev As Integer, _
        ByRef MyOut() As Integer, ByRef MyCount As Long, _
        ByRef MyLastI As Integer, ByVal mAddsTo As Integer, _
        ByRef mBackOut As Boolean)
 
'mylev starts at 0, and so does mycount
 
If MyLev > HowDeep Then
    If mAddsTo = 0 Then
        MyCount = MyCount + 1     'At this point, MyOut() contains a combination
    End If                            'of elements that add to the desired sum
Else
        'does something
    Dim MyI As Integer
    For MyI = (MyLastI) To (UBound(IN_Arr) - MyLev)
        'does something else
            Call NUM_SUM_COMBS_2(IN_Arr, HowDeep, MyLev + 1, MyOut, MyCount, _
                   MyI, mAddsTo - MyOut(MyLev), mBackOut)
            'does some more stuff
    Next MyI
End If
End Sub

Lets see how creative YOU are!
so far, compiled, mine produces 369569 combinations in about 4-5 seconds on my machine. but I'm still tweaking!


-Lou

[jemidiah]

With being able to use an element more than once, I used a random approach:

Dim i As Long
    Dim RndVal1 As Long
    Dim RndVal2 As Long
    Dim RndVal3 As Long
    Dim RndVal4 As Long
    Dim RndVal5 As Long
    Dim RndVal6 As Long
 
    Randomize
    For i = 1 To 266981
        RndVal1 = Int(Rnd * 60) + 1
        RndVal2 = Int(Rnd * 60) + 1
        RndVal3 = Int(Rnd * 60) + 1
        RndVal4 = Int(Rnd * 60) + 1
        RndVal5 = Int(Rnd * 60) + 1
        RndVal6 = Int(Rnd * 60) + 1
    
        If RndVal1 + RndVal2 + RndVal3 + RndVal4 + RndVal5 + RndVal6 = 150 Then MyCounter = MyCounter + 1
    Next i
    MyCounter = MyCounter * (61 ^ 6) / (i - 1)

I didn't make it generic, but it could be easily done. Oh, also, this gets more and more accurate the higher the upper bound of i is (at the sacrifice of speed).

[jian2587]

instead of using a matrix of numbers and going on sequentially to
grab numbers that'll add up to 150, how about given a number,
that is 150, and you try to search for number combinations that'll
sum up to that number? That is, through intelligent algorithms and
not sequentially?

And yes, that's precisely what u need, an algorithm, I'll try and
see if I can work out one.

[NotLKH]

That sounds like a good strategy, jian2587.
BTW, I've gotten mine down to about 4-5 seconds, but I've still got 1 tweak to do, and then I'm going to investigate rearranging a couple of steps that aren't needed until an individual combination has been made.


And, jemidiah?

It seems you've recently discovered the wonders of random numbers. They can certainly be usefull in many situations, but perhaps you should understand that, when I say "combination", I mean it in its purest mathematical sense, without repititions, and the order is not a consideration in the final output. So, basically, I'm looking for a conditional "All Combinations" Generator.


-Lou

[plenderj]

SQL Server could do it I'd say
I'm interested in giving it a go, but I don't understand your question fully. Can you give a stepthrough example for a few numbers ?

[NotLKH]

Ok.

Lets say I wanted to Generate every combination of 15 items taken 3 at a time, that add to 9.

And, Lets say the actual Values of the 15 items range from
1 to 15.

Their are 3 combinations that meet this criteria:

1, 2, 6
1, 3, 5
2, 3, 4

So, the goal of the progie is:

1) Return the count of all combinations of 15 items taken 3 at a time that add to 9, Generically, N items taken P at a time that add to S

2) Have each such Combination Generated physically generated. This is NOT meant to be a function on a calculator, so the count is just a return of every valid combination as they are generated. Ultimately, once a combination has been generated, it could be used as the input into some as yet undefined process.

3) All Such Combinations are not persistable. That is, It is not required to build an array of all such combinations. They only have to be in existance individually. For example, when all is said and done, the 3 combinations {Above} do not simultaneously exist. They Exist only Once, and destroyed to allow the next one to be generated. starts humming ending theme music to SOAP

4) The Progie must be capable to process 61 items {Number Vals of 1 thru 61} taken 6 at a time that add to 150.

There is a self imposed 5th goal, have the source numbers currently unused at the time the used ones are in a target aray be packed into the lower positions of the source array, but that'll be mentioned later.

Hows That?

BTW, I've localized my attempt into its own project, and it hums away at 4 to 5 seconds for the 6C61 = 150, meeting my 5th goal, and 2 seconds but not meeting my 5th goal

Just doing some cleanup, and perhaps I'll be satisfied with it soon.

BTW, if you Do have some way of confirming 369569 {See my Maths Question} , via a formula, perhaps you'd do so?


-Thanks

-Lou

[NotLKH]

Hmmm, shaved almost a second by moving some stuff to a bas.

Might as well post what I've got so far.


-Lou

[dis1411]

thats pretty cool that it only takes 4-5 sec on your comp
look at this post and see if it makes it even faster

the hard code takes about 1, i also get 369,569

Private Sub Command1_Click()
 
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
Dim e As Integer
Dim f As Integer
Dim l As Long
 
For a = 1 To 56
For b = a + 1 To 57
For c = b + 1 To 58
For d = c + 1 To 59
For e = d + 1 To 60
For f = e + 1 To 61
    If a + b + c + d + e + f = 150 Then
       
        l = l + 1
    End If
Next
Next
Next
Next
Next
Next
 
MsgBox Format(l, "#,#")
 
End Sub

i think that the fastest way that will allow u to enter how deep, the sum, and how many to try on the fly is to make a recursive function that in essence sets up nested for loops like the one above

[da_silvy]

Does it have to be vb?

[NotLKH]

da_silvy: Nope! Could be anything you want.

dis1411: Excellent! I doubt it could be any faster!

Now then. Your code specifically targets my test input, ie.. The numbers 1 thru 61, taken 6 at a time, adds to 150.

Think you could make it a little more generic? Make it so that your source is N elements, starting at K, ending with K + N - 1? {Instead of 61 elements, starting at 1, ending with 1 + 61 - 1?}

Also, allow it to take P at a time, instead of the fixed 6?

And, have the sum condition be a variable S, instead of a fixed 150? {N, K, P, and S are just suggested nomenclature, just meant to illustrate general variability}

And, One final thing? {Condition Number 5}

At the point where your code represents:

If a + b + c + d + e + f = 150 Then
       
        l = l + 1
    End If

Can you have a structure where the numbers that aren't a,b,c,d,e or F are in the first N - P elements of the structure, in ascending order?

With My code, although I'm sure its hardly decypherable, the In_Arr has all the used elements removed from their initial positions, and all the unused elements have shifted to the left to take up the positions originally held by the used elements.

I'm leading up toward haveing it return several groups of elements, each haveing potentially different sums, where the next group {x} is the combination of the elements of the original source, minus those used by the previously extracted groups, taken P_x at a time, adding to S_x.

Have Fun!

[NotLKH]

Originally posted by dis1411

look at this post and see if it makes it even faster

Thanks! I'll try this out tomorrow!


-lou

[NotLKH]

Originally posted by NotLKH
Thanks! I'll try this out tomorrow!


-lou

Yep!

I checked off everything in the advanced area
{Project->Project1 Properties->Compile->Advanced Optimizations}
And my time went from 4.2ish to 3.8ish seconds!

Very Nice!

Thanks again, dis1411!

[jian2587]

post up ur hardware and sys config so atleast i can know ur 3.8
secs is produced by wut sort of machine speed and i can compare
it with mine.

mine is a slow P4 2.0A Ghz, bus speed 533Mhz, 256MB 266Mhz
DDR SDRAM and WinXP Pro.

i actually have a new idea in my mind earlier on how to fine tune
this thin', but i haven't written any actual codes, still tweakin' it in
my head.

[jian2587]

on my P4 2.0A Ghz system,
ur prog gives me results as stated below:
in ide:10.3 seconds
compiled:1.578 seconds
compiled with all Advance Optimizations checked: 1.371 seconds

Pretty cool, huh?

[NotLKH]

So, at 600 Mhz, 3.8 seconds isn't too shabby!