Results 1 to 4 of 4
  1. #1
    New Lounger
    Join Date
    Oct 2001
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Why Does This Work? (VB6)

    This is a "DUH!" moment I know it but I just can't see how this works.

    I have been playing with programs to generate all combinations of a string of letters. I was trawling the net and I found the following routine:

    Public ITEM() As String
    Public QUEUE() As Integer
    Public TOTAL As Long

    Sub RunComb()

    Dim I As Integer
    Dim INPUTDATA As String

    INPUTDATA = "ABCDEFGH"

    TOTAL = 0
    ReDim ITEM(Len(INPUTDATA))
    ReDim QUEUE(Len(INPUTDATA))

    For I = 1 To Len(INPUTDATA)
    ITEM(I) = Mid(INPUTDATA, I, 1)
    Next I
    Call Comb(Len(INPUTDATA), 4, 1, 1)

    End Sub

    Sub Comb(M As Integer, N As Integer, LOW As Integer, LEVEL As Integer)

    Dim I As Integer
    Dim J As Integer

    For I = LOW To M - N + LEVEL
    QUEUE(LEVEL) = I
    If LEVEL < N Then
    Call Comb(M, N, I + 1, LEVEL + 1)
    Else
    TOTAL = TOTAL + 1
    Debug.Print TOTAL;
    For J = 1 To LEVEL
    Debug.Print ITEM(QUEUE(J));
    If J < LEVEL Then
    Debug.Print ", ";
    Else
    Debug.Print
    End If

    Next J
    End If
    Next I

    End Sub

    It works but I can't understand how. I understand the mechanics of the algorithm but the code execution eludes me.

    When the routine is seeded with "ABCDEFGH" and I single step through, it returns ABCD, ABCE, ABCF, ABCG and ABCH as expected. It is at this point I fail to understand the execution. The outer loop "FOR I = LOW to M - N + LEVEL" completes (as I=9 ie > M - N + LEVEL) and pressing F8 again highlights END SUB. When I press F8 again, expecting the routine to stop, the execution point returns to "NEXT I" and the value of I has changed to 3. The program then continues, stopping only when it has returned all valid combinations of the input string.

    As I said, I am sure it is a "DUH!" thing but I would appreciate some enlightenment so I can apply hand to forehead at speed and continue with my life.

    regards
    Grant

  2. #2
    Plutonium Lounger
    Join Date
    Mar 2002
    Posts
    84,353
    Thanks
    0
    Thanked 29 Times in 29 Posts

    Re: Why Does This Work? (VB6)

    The Comb procedure is recursive, that is, it calls itself repeatedly:

    Sub Comb(M As Integer, N As Integer, LOW As Integer, LEVEL As Integer)
    ...
    For I = LOW To M - N + LEVEL
    QUEUE(LEVEL) = I
    If LEVEL < N Then
    Call Comb(M, N, I + 1, LEVEL + 1)
    Else
    ...

    In the RunComb procedure, Comb is called with 1 as LEVEL argument. The above loop calls Comb several times with LEVEL = 2, that in turn calls Comb with LEVEL = 3, etc. This stops when LEVEL has the same value as N (4 in this example)

  3. #3
    New Lounger
    Join Date
    Oct 2001
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Why Does This Work? (VB6)

    Thanks for the quick response.

    I hadn't fully grasped the full implications of the recursion. Now that I have I will award myself a "quasi-DUH!". ie "Oh, that's how it works - DUH!" <img src=/S/stupidme.gif border=0 alt=stupidme width=30 height=30>

    Thanks again
    Grant

  4. #4
    Plutonium Lounger
    Join Date
    Mar 2002
    Posts
    84,353
    Thanks
    0
    Thanked 29 Times in 29 Posts

    Re: Why Does This Work? (VB6)

    Don't blame yourself, recursion isn't the easiest concept to grasp.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •