get all combination of a set of numbers (1 Viewer)

[lala]

omg, the website StackOverflow, thats where it cams from?)))))))))

 

[gemma-the-husky]

recursion works by a procedure repeatedly calling itself. note that not every language permits recursion. Because many structures are recursive in nature, this idea lends itself to the use of recursion. eg in this case, a "legal" combination is based on extending a string by each of the next possible terms that could be in the string - note that recursion automatically ensures that each combination is considered/processed once and once only. A recursive algorithm is also very code "light" - you can do often do things simply with recursion, that are hard to do procedurally.

so in this case, you start with each of the possible first values in the combination

so - lets say you want to select 5 items from 7 so in this case the first value can only be any of item 1 thru 3 (starting with item 3 gives you ONLY combination 3,4,5,6,7 - you cant start with item 4 - becasue you cant get a set of 5 values starting with 4)

so, in this case you need to start with each of values 1,2,3 - which means the process calls itself, starting with the partial string "1", "2" and "3" in each case

so when it starts with a string of "1" the recursive procedure then next calls itself with each of the possible values that will work for the next term of the series - so this time start with "12", "13" and "14" - (again not "15", because you cant get a string of 5 values starting with "15". Then "12" extends itself to "123", "124" and "125" - and so on

All the programmer has to find is a way of controlling the recursion, and a way of stopping it continuing - in this case when the string reaches the required length.


so recursion involves a procedure calling itself repeatedly, and to do this it has to "save" details of the parameter arguments, and local copies of the variables for this instance of the procedure. A stack is a structure that saves things in order, and then removes them in the reverse order (often called push and pop)

now if you wanted to perm say 5 items form 7, this yields 35 results (7x6x5 / 1x2x3 ) and this won't cause a stack problem.

if however you want to select say 8 from 25 items

then this gives 25x24x23x22x21x20x19x18 / 1x2x3x4x5x6x7x8 combinations = 1081575 - which almost certainly will cause a stack overflow - as well as taking a long time to generate the answers.

Because in this instance, I used a string of numbers, it only works for values 1 to 9, as I was just considering the length of the string. Having an item 10, would cause problems with this- but easily overcome by treating each term as a 2 digit number, or by using letters instead of numbers.

 

[gemma-the-husky]

just to make it clear - these bits set up the logic

Option Compare Database
Option Explicit

Dim result(1000) As String  [COLOR="Red"]'to record the strings returned by the alogrithm[/COLOR]
Dim maxresult As Long [COLOR="red"]'to count the number of strings found[/COLOR]

[COLOR="Blue"]'{sub combine not shown here}[/COLOR]

Sub main() [COLOR="red"]'call the process[/COLOR]
Dim x As Long [COLOR="red"]'just used to display the result[/COLOR]
Dim s As String 

maxresult = 0 [COLOR="red"]'to start - clear the combination count to zero[/COLOR]

[COLOR="red"]'now initiate the recursion
'the first term is the number of items to select
'the second term is the number of terms to select from
'the third term is a null string to start from[/COLOR]

[COLOR="red"]'eg[/COLOR]
Call combine(3, 7, "") [COLOR="red"]'selects 3 from 7 (7x6x5 / 1x2x3 = 35 combinations)[/COLOR]

[COLOR="red"]'or[/COLOR]
Call combine(5, 9, "") [COLOR="red"]'selects 5 from 9 (9x8x7x6x5 / 1x2x3x4x5 = 126 combinations)[/COLOR]

[COLOR="red"]'now show the results[/COLOR]s = ""
For x = 1 To maxresult
    s = s & result(x) & vbCrLf

Next
MsgBox (maxresult & " permutations" & vbCrLf & vbCrLf & s)

End Sub

 

[lala]

Gemma, first of all I can’t find the words to thank you for taking the time and the effort to explain this in so much detail and for making it so clear. i’m really speechless, not only you handed me a solution but you then went out of your way to explain every bit of it.
Thank you doesn’t say it but I’m gonna say it anyway)))))))))))

I understood most of what you wrote, and whatever I didn’t understand was only because I don’t know the simplest things, not because you didn’t explain it well enough.

I’m not trying to make you spend more time on me, I just want to let you know that I read your posts thoroughly and so I’m posting a few questions

recursion works by a procedure repeatedly calling itself.

How’s recursion different from a loop? What makes your code recursive is I guess what I’m asking, I recognize a loop and that’s it)))))))))))

so - lets say you want to select 5 items from 7 so in this case the first value can only be any of item 1 thru 3 (starting with item 3 gives you ONLY combination 3,4,5,6,7 - you cant start with item 4 - becasue you cant get a set of 5 values starting with 4)

Understand this part

so, in this case you need to start with each of values 1,2,3 - which means the process calls itself, starting with the partial string "1", "2" and "3" in each case

so when it starts with a string of "1" the recursive procedure then next calls itself with each of the possible values that will work for the next term of the series - so this time start with "12", "13" and "14" - (again not "15", because you cant get a string of 5 values starting with "15". Then "12" extends itself to "123", "124" and "125" - and so on

so to keep going we’d have 123 extending to 1234,1235 and 1236, right? And then 1234 becomes 12345, 12346 and 12347 and this give me my first 3 combinations, and then the program goes on to what?
Let’s say it then goes on to working on 1235, so 1235 becomes 12356 and 12357 (2 more combos) and then 1236 becomes 12367 (1 more combo)

Then on to 124? And how does it make sure that the values don’t repeat

And if I understood the numbers right then you don’t even know how much of a compliment that is, I’m really slow)))))))))

And again, thank you thank you!!!! On to studying your code now

 

[lala]

Gemma, what's your background if you don't mind me asking? i've seen a lot of your answers on this forum, you've helped me a few times before too. and the impression i got about you is that there's no question that you can't answer. are you self-taught? what about the math part of it? hope i'm not being too nosy, if i am - just ignore the post.

 

[gemma-the-husky]

recursion different to a loop

if you tried to set up a loop to do this, you would find it very awkward, as the loop would change depending on how many items you were trying to select and from what population. I can't think offhand how I would do it in that way (as you found) , but I am sure it is possible

with recursion , the recursive procedure just calls itself as often as it needs to, and determines when to stop by itself - so it is quite different to a loop - there is no iteration control count anywhere


recursion process

the sub/function COMBINE has a line in that says

CALL COMBINE (the call is superfluous, but I am used to using them) - that IS the recursion process

so - lets say we are generating 5 items from 7

so, the sub COMBINE starts with a blank string - as we have seen, this string has to start with 1,2 or 3 so in each case we call COMBINE again, but this time with a string of "1", "2" and "3" respectively

so in the first case COMBINE calls itself with a string of "1", and now the COMBINE process calls itself AGAIN, this time with strings that develop from "1", therefore "12", "13", "14" and so on - Now this would go on forever unless we stop COMBINE calling itself. And we do this by examining the length of the string

when we get the first string as "12345" - instead of adding another term to it - we just say - "stop, as the string is now 5 terms long"

why are there no repeats

there just aren't - there can't be. The mechanism examines the tree of possibilities, and only visits each branch once.

Have you tried it

here's the combine function again with a couple of msgboxes, so you can see how it evaluates the possibilites. I have actually moved the termination check down into the bit that determines whether to drop down another level. The msgboxes should make it clear how it is developing the strings.

Function combine(required As Long, max As Long, combo As String) As String
Dim x As Long
Dim startfrom As Long
Dim newstr As String
   
If Len(combo) = 0 Then
    startfrom = 0
Else
    startfrom = CLng(Right(combo, 1))
End If


For x = startfrom + 1 To ((max - required) + Len(combo) + 1)
    newstr = combo & CStr(x)

[COLOR="Blue"]'now determine whether the recursion is finished - or whether we need to drop dpwn another level[/COLOR]
    If Len(newstr) = required Then
[COLOR="Blue"]'if so store this result in the final array[/COLOR]
 [COLOR="red"]       MsgBox ("End sequence " & newstr)[/COLOR]
        maxresult = maxresult + 1
        result(maxresult) = combo
    Else
[COLOR="Red"]        MsgBox ("Examining Strings Starting With " & newstr)[/COLOR]
        Call combine(required, max, newstr)
    End If
Next
End Function

Think of this logic applied to a folder structure -

sub examinefiles(basefolder)
for each file in the basefolder
    if it is a folder then
           examinefiles (for the folder)
    else
           list this file   
    end if
next
end sub

now we have the DIR() command in VBA which you would think you could use to do this -but unfortunately the DIR() command supplied with VBA is NOT recursive - ie it can't call itself, so this logic isn't available to process all the files in a given folder structure - which makes it surprisingly hard to achieve

 

[lala]

recursion different to a loop

if you tried to set up a loop to do this, you would find it very awkward, as the loop would change depending on how many items you were trying to select and from what population. I can't think offhand how I would do it in that way (as you found) , but I am sure it is possible

you mean the only problem is that you won't know how to explain to the loop when to stop? i can't believe that i'm actually understanding everything you're saying)))))))))))))) i'm so hyped because i'm really new to vba, i know almost nothing and i think i understand everything you say

 

[lala]

yes, i just ran it and i see now the order of it, Gemma, thank you so much!! i appreciate it so much, i actually understand how this is done now! thank you for your infinite patience

 

[gemma-the-husky]

you mean the only problem is that you won't know how to explain to the loop when to stop? i can't believe that i'm actually understanding everything you're saying)))))))))))))) i'm so hyped because i'm really new to vba, i know almost nothing and i think i understand everything you say

i mean't more that if you were trying to generate the possible combinations by "normal" coding, then writing an algorithm to do it, would not be very easy. Even if you know you want in particular, say, just every combination of 3 items from a population of 7 - it isn't easy to write code to do this.

you would probably need 3 nested for loops - one for each item - but it is still difficult to do. And then this version wouldn't work if you wanted a different number than 3 items - so the entire problem becomes very intractable, for a general solution.

That's probably why you couldn't find a non-recursive solution.

 

[lala]

Function combine(required As Long, max As Long, combo As String) As String
Dim x As Long
Dim startfrom As Long
Dim newstr As String
   
If Len(combo) = 0 Then
    startfrom = 0
Else
    startfrom = CLng(Right(combo, 1))
End If


For x = startfrom + 1 To ((max - required) + Len(combo) + 1)
    newstr = combo & CStr(x)

'now determine whether the recursion is finished - or whether we need to drop dpwn another level
    If Len(newstr) = required Then
'if so store this result in the final array
        MsgBox ("End sequence " & newstr)
        maxresult = maxresult + 1
        result(maxresult) = combo
    Else
        MsgBox ("Examining Strings Starting With " & newstr)
        Call combine(required, max, newstr)
    End If
Next
End Function

isn't this the function that you're talking about? i don't see how it's different from a loop, i looked at it over and over all i see is this

For x = startfrom + 1 To ((max - required) + Len(combo) + 1)
next

isn't this a loop?

 

[lala]

i thought that any code that repeats itself over and over until you tell it to stop is a loop, no?

 

[lala]

i probably sound like a total idiot, but believe it or not i wrote many programs, it's just, i'm sure you know, in access there are many ways to do one thing. and even though most of my solutions weren't pretty they worked. VBA is new to me, only the last 2 years, and i'm learning by googling and taking different pieces of code and customizing it. that's why when i see people here that seem to know everything i start to get a complex of some sort))))

 

[gemma-the-husky]

yes - you are right, of course, it is an iterative construct

what i meant though was that normally you have 2 loop controls

for ... next - which carries out an instruction for a given number of times

do loop
which includes both repeat until, and while wend which carries out an instruction until it reaches a termination test.

and recursion is not generally considered as a normal iterative construct.

but writing algorithms to manage data that is recursive in nature, is very difficult without using a recursive technique.

as I said, i think the code to write a generalised solution to build an array of potential combinations without using recursion would be very difficult to write - although I am sure it is possible




--------------
eg a typical recursive structure is a tree.

a binary tree has two possibilities at each node

so from the root you can either go left or right
from the next step down you can either go left or right
so assume you go left at each step
now when you reach the end and there are no more children, you go back up to the last node you visited - and now you need to go right, and see what is down there

eg take this tree (i can't get this formatted to display cleanly, but hopefully you get the idea)

                                          1
                                    2a                          2b
                             3a                           3b           3c 
                       4a        4b                                 4c         4d
                   5a  5b     5 c  5d                        5e    5f    5g    5h
                                                                                     6a

in order to traverse the whole tree, you need an algorithm that starts at the top, (the root - node 1) and visits every node in turn

again, this is extremely difficult if you just try to use for..next or other loops, and without using recursion, and trivial with it.

Just consider each junction point as a "node" exactly the same as any other node - the only special case is the "root", which has no parents. So from any node, we step to each node down the treee, and then reconsider this as its own "root node"

- its then the recursive logic is. (I think from memory)

sub examine_node (nodebase as node)
if node has children then 
   process this non-leaf node
   for each child_node
      'note this is generalised for trees with any number of children at any node
      'the recursion - examine this sub tree ....
      call examine_node(child_node)
   next
else
  process this leaf node
end if

so given the tree above this will wak the tree in order

1, 2a, 3a, 4a, 5a, (back to 4a), 5b, (back to 4a), (back to 3a), 4b, 5c, (back to 4b), 5d, (back to 4b), (back to 3a), (back to 2a), (back to 1) ... and so on, now down the right tree.

This sort of structure appears in many cases in computing - eg typically indexes are trees are some sort - and xml and html files are hierarchical tree structures.

 

[lala]

i think i understand, loop will loop through until you tell it to stop, recursion will keep calling itself until there's more stuff to examine. here's another stupid question, what in your code makes it recursive? is it the fact that you have the if..then..else inside the loop to see if it should keep going or what?? i read everything you say and i understand it, but when i try to go and match it to your code - i get lost.

sub examine_node (nodebase as node)
if node has children then 
   process this non-leaf node
   for each child_node
      call examine_node(child_node)
   next
else
  process this leaf node
end if

for example, i understand what you're saying here and how it relates to the tree. but if i saw this code somewhere i'd think it's a regular if then else and a loop.
which part of it makes this code recursive? can you point to the line or the word?
is it the fact that the regular loop would say For intCounter = 2 to 25 and yours only has for each node? and assumes that when there's nothing else to examine it will stop? then another stupid question, what in the code makes it know that?
this is what happens when i try to read code books to learn, i start to get questions like this and there's noone to ask so i just go back to google, copy, paste, customize. the fact that everyone else understands makes me think that it's not the books, it's me. sorry for taking so much of your time.

 

[stopher]

which part of it makes this code recursive? can you point to the line or the word?

It's recursive because it calls itself. Dave has written a function called combine. However, within that function, he calls the function combine i.e. it's calling itself. See how "examine node" is repeated in the pseudo code.

Chris

 

[lala]

so the fact that you can call the function inside yourself makes it recursive? and some languages don't allow that? is it really that simple?

 

[lala]

the reason i said that about languages was because another question was that i see on the net that some languages don't allow recursion and since i couldn't understand what it is that makes the code recursive i couldn't understand what it was that some languages don't allow.

 

[stopher]

so the fact that you can call the function inside yourself makes it recursive? and some languages don't allow that? is it really that simple?

Yes .

Here’s another explanation of how the recursion works…

Consider the string 1234. We might write a function to return the combinations as Comb(“1234”) and we’d expect that function to return all the combinations.

But the combinations of “1234” i.e. Comb(”1234”) can thought of as:

1 & Comb(“234”) ….. 1 & all possible combinations of the remaining characters.
and
2 & Comb(“134”) ….. 2 & all possible combinations of the remaining characters.
and
3 & Comb(“124”) ….. etc
and
4 & Comb(“123”)

In other words, Comb("1234") will call Comb("234"), Comb("134") etc. So the problem has been broken down a level.

Equally, Comb(“234”) – see above, can be thought of as:

2 & Comb(“34”)
and
3 & Comb(“24”)
and
4 & Comb(“23”)
Etc

Eventually we’ll get to looking for combinations of a single character e.g. “4”. At this point the Comb function DOES NOT attempt to call Comb again. Its knows it is at the bottom of the tree because the string length is 1.

 

[lala]

omg, i put Gemma through all this horror and it turns out to be this easy???

got it but in this case it permutes it, right? so 1234 and 4321 will be 2 different combinations. for my purposes i only needed each combination once.
but i see how they all work now.
i wish i had someone like you guys that had nothing better to do but explain everything i didn't understand like this))))))))) do the people you work for realize what they have? i'm told i'm brilliant by everyone i've ever wrote programs for and you saw my level of knowledge.

 

[gemma-the-husky]

here's an example of trying to use DIR() to recursively examine all the files in a tree.

so start at "C:\"

in my system the first file is "2007 Office System Developer Resources" - which is a subfolder - so the code examines this subfolder. In there the first file is "2007OfficeIconsGallery", another folder - so the code now examines this folder. In there is is just one normal file and no more folders so the function lists the contents of this last folder - and then attempts to go back up the recursion to examine any more items within the "2007OfficeIconsGallery" ... and so on

However, because you cannot have multiple concurrent Dir sessions - the previous Dir cursor is no longer where it was when you left it - and so it now crashes the routine

So this otherwise neat way of traversing a folder/file structure fails because Dir is non recursive - as is noted at the bottom of the help entry!

Sub listdirectory(root As String)
Dim fname As String
Dim s As String

    MsgBox ("Checking directory " & root)
    
    s = ""
    fname = Dir(root, vbNormal + vbDirectory)
    If fname = "" Then Exit Sub  ' no files in this folder
    
    While fname <> ""
        'if this file is a folder then call this procedure again to
        'go down the next folder. Use getattr to see if this is a folder
        If (GetAttr(root & fname) And vbDirectory) = vbDirectory Then
            If fname <> "." And fname <> ".." Then
                s = s & fname & "   (subfolder) " & vbCrLf

[COLOR="Red"]                'comment these next two lines out to see it working normally[/COLOR]                   
                 MsgBox ("Examining subfolder " & root & fname & "\")
                listdirectory (root & fname & "\")
            End If
        Else
            s = s & fname & vbCrLf
        End If
        
        On Error GoTo fail
        
        'this is the problem
        'dir is not recursive
        [COLOR="Red"]fname = Dir[/COLOR]
   Wend
   
   MsgBox ("Completed examination of " & root & vbCrLf & vbCrLf & _
        "Results were: " & vbCrLf & vbCrLf & s)

   Exit Sub
    
fail:
    MsgBox ("Error: " & Err & "  Desc: " & Err.Description & vbCrLf & vbCrLf & _
        "Results were: " & vbCrLf & vbCrLf & s)

End Sub


Sub directory_main()
'include whatever folder you want to check here ...
 listdirectory ("C:\")
End Sub