1. ## recursive functions

hi;

i am a financial analysist trying to develop windows applications in vb.net. I have been stuck with a situation that i can not resolve without the help. Here is the problem.

I have 3 variables. Lets call it "a", "b" and "c". These 3 variables can "independently" have 3 different values. Lets say: "1", "6" and "10". when you think of them as combination; there are (3^3) 27 combinations. I am told that it can be done through the recursive functions. However i am not a good developer to handle with that. Would u please help me?

- 3 variables and 3 different values are simplified. In fact; the numbers of variables and different values can vary.

- i know only the language, visual basic in .net; please dont answer in other coding languages.

additional note: i am going to put the these combinations in the string format into a collection.. for example "1;1;1", "1;6;1", "1;6;10".. and so on..  Reply With Quote

2. ## Re: recursive functions

Is this what you want?

Code:
```        Dim var3() As String = New String() {"1", "6", "10"}

Dim output As New System.Text.StringBuilder
Debug.WriteLine("")
For Each c1 As String In var3

For Each c2 As String In var3

For Each c3 As String In var3
output.Length = 0
output.AppendFormat("{0};{1};{2}", c1, c2, c3)
Debug.WriteLine(output.ToString)
Next
Next
Next```
Here is the output

Code:
```1;1;1
1;1;6
1;1;10
1;6;1
1;6;6
1;6;10
1;10;1
1;10;6
1;10;10
6;1;1
6;1;6
6;1;10
6;6;1
6;6;6
6;6;10
6;10;1
6;10;6
6;10;10
10;1;1
10;1;6
10;1;10
10;6;1
10;6;6
10;6;10
10;10;1
10;10;6
10;10;10```  Reply With Quote

3. ## Re: recursive functions

thanks for your reply; but i guess not; because it wont work if i have 4 variables and 4 different values, will it? Since both the number of variables and values can vary..

u have made 3 loops, is it because there are 3 variables ("a","b" and "c")?

and also what do the characters, "c1", "c2" and "c3" refer to? (1,6,10) or (a,b,c)?

i am working at the moment; i will try it after i go home..  Reply With Quote

4. ## Re: recursive functions

also output is what i really want..  Reply With Quote

5. ## Re: recursive functions Originally Posted by cem babaeren thanks for your reply; but i guess not; because it wont work if i have 4 variables and 4 different values, will it? Since both the number of variables and values can vary..

u have made 3 loops, is it because there are 3 variables ("a","b" and "c")?

and also what do the characters, "c1", "c2" and "c3" refer to? (1,6,10) or (a,b,c)?

i am working at the moment; i will try it after i go home..
In your first post you should have made it clear that the number of variables could have been from ? to ?.  Reply With Quote

6. ## Re: recursive functions Originally Posted by cem babaeren hi;

i am a financial analysist trying to develop windows applications in vb.net. I have been stuck with a situation that i can not resolve without the help. Here is the problem.

I have 3 variables. Lets call it "a", "b" and "c". These 3 variables can "independently" have 3 different values. Lets say: "1", "6" and "10". when you think of them as combination; there are (3^3) 27 combinations. I am told that it can be done through the recursive functions. However i am not a good developer to handle with that. Would u please help me?

- 3 variables and 3 different values are simplified. In fact; the numbers of variables and different values can vary.

- i know only the language, visual basic in .net; please dont answer in other coding languages.

additional note: i am going to put the these combinations in the string format into a collection.. for example "1;1;1", "1;6;1", "1;6;10".. and so on..
isn't it clear? it would be any number..  Reply With Quote

7. ## Re: recursive functions

Here is a Snippet from jmc 5 years ago converted to vb.net It should be very easy to adapt to what you want to do.

Code:
```  Dim finalLength As Integer = 10
' The length of the final strings.
Dim characters As String() = New String() {"a", "b", "c", "d", "e"}
Dim existingStrings As System.Collections.Specialized.StringCollection
Dim newStrings As New System.Collections.Specialized.StringCollection()

For len As Integer = 2 To finalLength
' Start a new collection of strings based on the existing strings.
existingStrings = newStrings
newStrings = New System.Collections.Specialized.StringCollection()

' Concatenate every string of length (len-1)...
For Each str As String In existingStrings
' ...with every character...
For Each ch As String In characters
' ...to create every possible string of length len.
Console.WriteLine(str & ch)
Next
Next
Next```  Reply With Quote

8. ## Re: recursive functions Originally Posted by cem babaeren isn't it clear? it would be any number..
It was there, that is clear.  Reply With Quote

9. ## Re: recursive functions

hmmm... as a loop it's farily simple... as a recursive function.... hmmm... this'll give the back of my brain something to think about today...

-tg  Reply With Quote

10. ## Re: recursive functions

I think I managed to adapt HeapPermute algorithm and make a generic class out of it.

Some theory can be found here:
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

vb Code:
`''' <summary>    ''' A generic class that encapsulates a HeapPermute algorithm (I think)    ''' </summary>    ''' <typeparam name="T"></typeparam>    ''' <remarks>    ''' With this class you can obtain an IEnumerable which contains all the permutations of the given sequence of values.    ''' </remarks>    Class Permuter(Of T)        ' VS 2010 Auto implemented        Public Property Sequence As IEnumerable(Of T)         Public Function GetAllPermutations() As IEnumerable(Of IEnumerable(Of T))            Return GetAllPermutations(_Sequence)        End Function         Private Function GetAllPermutations(ByVal values As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))            Dim ret As New List(Of List(Of T))             Select Case values.Count                Case 0                    Return ret                Case 1                    ret.Add(New List(Of T) From {values(0)})                    Return ret                Case Else                    Dim GetExcluded = Function(sourcevalues As IEnumerable(Of T), excluded_element As T) As IEnumerable(Of T)                                          Return From vals In sourcevalues Where Not vals.Equals(excluded_element)                                      End Function                     For Each value As T In values                        Dim tempret As IEnumerable(Of IEnumerable(Of T)) = GetAllPermutations(GetExcluded(values, value))                        For Each tempelement In tempret                            Dim templist As New List(Of T)                            templist.Add(value)                            templist.AddRange(tempelement)                            ret.Add(templist)                        Next                    Next                    Return ret            End Select         End Function    End Class`

Test program:

vb Code:
`Sub Main()        Dim p As New Permuter(Of Integer)        Dim sequence() As Integer = {1, 2, 3, 4}         p.Sequence = sequence         Dim ret As IEnumerable(Of IEnumerable(Of Integer)) = p.GetAllPermutations         For Each permutedsequence In ret            For Each value As Integer In permutedsequence                Console.Write(value.ToString & "; ")            Next            Console.WriteLine()        Next        Console.ReadLine()    End Sub`

Test output:
Code:
```1; 2; 3; 4;
1; 2; 4; 3;
1; 3; 2; 4;
1; 3; 4; 2;
1; 4; 2; 3;
1; 4; 3; 2;
2; 1; 3; 4;
2; 1; 4; 3;
2; 3; 1; 4;
2; 3; 4; 1;
2; 4; 1; 3;
2; 4; 3; 1;
3; 1; 2; 4;
3; 1; 4; 2;
3; 2; 1; 4;
3; 2; 4; 1;
3; 4; 1; 2;
3; 4; 2; 1;
4; 1; 2; 3;
4; 1; 3; 2;
4; 2; 1; 3;
4; 2; 3; 1;
4; 3; 1; 2;
4; 3; 2; 1;```  Reply With Quote

11. ## Re: recursive functions

This is a test for the sentence "The quick brown fox jumps over the lazy dog" (N=9)

vb Code:
`Sub Main()        Dim p As New Permuter(Of String)        Dim sequence() As String = "The quick brown fox jumps over the lazy dog".Split(New Char() {" "c})         p.Sequence = sequence         Dim t As New System.Diagnostics.Stopwatch         t.Start()        Dim ret As IEnumerable(Of IEnumerable(Of String)) = p.GetAllPermutations        t.Stop()         Console.WriteLine(String.Format("Total number of permuted sequences: {0}, total time: {1} milliseconds.", ret.Count, t.ElapsedMilliseconds))         Console.ReadLine() End Sub`

Output:

Code:
`Total number of permuted sequences: 362880, total time: 17639 milliseconds.`
9! = 362880
Tested on HP Pavilion tx 2000 in debug mode on Windows 7 x64  Reply With Quote

12. ## Re: recursive functions

thanks to all;

i will take into consideration all suggestions. i hope i will do it correctly..  Reply With Quote

13. ## Re: recursive functions

Lol something weird happens on my pc. I use windows 7 X64.
When i run the example that you did targeting the X86 cpu it Takes 98347 ms to run.
But when i target the X64 cpu it takes 2873 ms.  Reply With Quote

14. ## Re: recursive functions

I should probably warn that my example works only when sequence contains unique elements. It means it won't work with something like {1, 1, 2, 2, 3, 3}.
You should change the GetExcluded lambda in order to process such sequences. I used lists for temporary storate while it would be possibly better to use arrays or dictionaries.  Reply With Quote

15. ## Re: recursive functions

dear blindsniper; i tried yours first:

Code:
```
Dim finalLength As Integer = 10

Dim characters As String() = New String() {"1", "2", "3", "4", "5"}
Dim characters2 As String() = New String() {"a", "b", "c", "d"} 'my variables
Dim existingStrings As System.Collections.Specialized.StringCollection
Dim newStrings As New System.Collections.Specialized.StringCollection()

Dim temp_str As String
Dim temp_str_splitted() As String
Dim count As Integer
count = 0
For len As Integer = 2 To characters2.Count
' Start a new collection of strings based on the existing strings.
existingStrings = newStrings
newStrings = New System.Collections.Specialized.StringCollection()

' Concatenate every string of length (len-1)...
For Each str As String In existingStrings
' ...with every character...
For Each ch As String In characters
' ...to create every possible string of length len.
temp_str = str & ";" & ch
temp_str_splitted = Split(temp_str, ";")
If UBound(temp_str_splitted) + 1 = 4 Then
count += 1
End If

Console.WriteLine(str & ch)
Next
Next
Next
the reason why i used the if condition (ubound) is that i only want the strings which have 4 length.

I firstly wrote "For len As Integer = characters2.Count To characters2.Count" but it gave me only the results about the strings having 2 length. Then i wrote the above and put the if condition; it gave me the 5^4 (625) results what i really wanted.

Do u have any opinion why "For len As Integer = characters2.Count To characters2.Count" gave different result?? Or do you have any other suggestions which make my code more efficient or fast?

now; it is time to try to adopt Cicatri's suggestion..  Reply With Quote

16. ## Re: recursive functions

dear cicatrix;

My final code is the below:

Code:
```    Public Shared Sub calculate(ByVal number_of_variables)

Dim combination_list As New Collection
Dim starting_value As Integer
Dim ending_value As Integer
Dim incremental_value As Integer
Dim temp_value As Integer
Dim value_list As New Collection

starting_value = 1
ending_value = 10
incremental_value = 3
temp_value = starting_value

Do Until temp_value > ending_value
temp_value += incremental_value
Loop

Dim newStrings As New Collection
Dim temp_str As String
Dim temp_str_splitted() As String
Dim count As Integer

For i = 1 To value_list.Count
Next

For len As Integer = 2 To number_of_variables '"a","b","c","d", "e"
For i = 1 To newStrings.Count
Dim str As String
str = newStrings(i)
For j = 1 To value_list.Count
Dim ch As String
ch = value_list(j)
temp_str = str & ";" & ch
temp_str_splitted = Split(temp_str, ";")
If UBound(temp_str_splitted) + 1 = number_of_variables Then
count += 1
End If

Next
Next
Next
End Sub```
I am putting all combinations into the "combination_list" to use after to gerenrate new series. I used "If UBound(temp_str_splitted) + 1 = number_of_variables" since i only need the combinations having the lenght "number of variables", not lower than it.

In my example i have 5 variables and 4 different values. That makes 4'5 = 1024.

However i have a problem: i want to create billions of combinations. (let's make "incremental_value = 0.01 instead of incremental_value = 3) But it gives the errror, "out of memory exception".

How can i handle that?

Will your code able to handle this error? If so; i will try your code again..  Reply With Quote

17. ## Re: recursive functions

Hi, I'm a bit late to the show. When dealing with large numbers of permutations it can become impracticable to store all the possibilities. There are algorithms out there that calculate the Nth permutation (there used to be a very good one on Wikipedia that could handle non unique elements, but it has sadly now gone, those damn pure math fascists) If you are dealing with billions of combinations then such an algorithm might be useful to you. I've a version I could translate to vb.net this evening.

Alternatively an algorithm could be written to generate the permutations in manageable batches, say 1'000'000 at a time. Some of the algorithms above could be adapted for this.  Reply With Quote

18. ## Re: recursive functions

dear Milk;

suppose that:

a: consumption
b: income
c: age
d: household size
e: education

i have montly real data btw 1990 and 2010. i want to generate new set of data referring to the actual one by using the combination list. For example; one of the items in the list is: "1.2;2;3;4.1;2" Then; my new set of data is calculated as the following:

a' = a * 1.2
b' = b * 2
c' = c * 3
d' = d * 4.1
e' = e * 2

My code currently working is able to handle small size of combinations. But i need more because i am not only interested in integer and double numerics but also i want "log" and "ln" versions.

u talked about manageable patches. You mean; for example; when "combination_list.count = 1.000.000"; i will stop and do further calculations and then clear the list and start at where i previously stopped???

i really appreciate if u translate the version to vb .net. I really stuck with the billions of comibantions..  Reply With Quote

19. ## Re: recursive functions

apologies, had a late one at work, no coding tonight.

I can't find the Nth permutation algorithm although I know I have it somewhere (just not in my permutations folder) I'll have another look when I'm less tired.

Here is a link to some VB6 next n permutations code (i.e. permutations in batches) The class is untranslatable, it uses an array hack which simply can't be done in Net. The module that does the core work can be translated and made much shorter. Its based on this from the wikipedia article.

Note the link to the SteinhausJohnsonTrotter algorithm I've not come across it before, it looks quite cool.

Soz again, won't be working quite so late tomorrow.  Reply With Quote

20. ## Re: recursive functions

milk;

did you have a chance to search the code in other folders?

i have investigated the links given but i dont have enough coding background to somehow handle with the memory exception problem..  Reply With Quote

21. ## Re: recursive functions

Really sorry for the delay, I've some quite serious family nonsense going on.

Here are four static methods (two being public) that could be used to provide the backbone for a permutations class. It is an untested translation. I've included a reverse sequence method because in C# at least it is considerably faster than the native Array.Reverse().
Code:
```	Public Shared Function Permute(sequence As Char()) As Boolean
Dim ub As Integer = sequence.Length - 1
Dim k As Integer = ub

For k = ub - 1 To 0 Step -1
If sequence(k) < sequence(k + 1) Then
Dim l As Integer = ub
Dim v As Char = sequence(k)
While v >= sequence(l)
l -= 1
End While
swap(sequence(k), sequence(l))
reverse(sequence, k + 1, ub)
Return True
End If
Next
Return False
End Function

Public Shared Sub ResetSequence(sequence As Char())
Array.Sort(sequence)
End Sub

Private Shared Sub reverse(sequence As Char(),byval lb As Integer,byval ub As Integer)
While ub > lb
swap(sequence(lb), sequence(ub))
lb+=1
ub-=1
End While
End Sub

Private Shared Sub swap(ByRef a As Char, ByRef b As Char)
Dim swp As Char = a
a = b
b = swp
End Sub```
I've used a sequence of char because it can convert to string very quickly. To use you would take any char sequence, sort it using ResetSequence() (giving you permutation 1) and then repeatedly call Permute() to order the sequence to the next permutation. Permute returns false when there are no more permutations. Hopefully you can see how to use it.

Sorry again for the delay.  Reply With Quote

22. ## Re: recursive functions

i am sorry for your problems. thats ok for the delay.

1) "sequence as char()" contains what? variables? values? or the combination string which i finally want?.. you have defined l and v as integer. Then i think the answer is "values". If so there is a problem. The "values" should necessarily not only be integer; but also be double or even string to define "log" and "ln" versions. That was my fault; i should have previosuly cleared it out.

2) My code is currently creating combinations based on number of variables and values in an inefficient way. Whenever i create one combination string, i then do the othe stuff and come back to create the other combination string to go on. it currently works and calculates 750.000 - 800.000 combinations and do stuff per hour. I couldn't find where this combination is created in your code? and also i couldn't understand when to call the function "permute" since it is boolean.

Anyway; let me try it at the weekend and see what happens..

thanks..  Reply With Quote

23. ## Re: recursive functions

Hi, Permute() rearranges the passed Char array to the next permutation in lexicographical order. It returns false when there are no more permutations. The Char array rather like a String consists of Unicode characters. Unlike a String (which is immutable), the characters in a Char array can be swapped around.

One way to create a char array is like this...
Code:
`Dim MyCharArray() As Char = "bananas".ToCharArray()`
One way to convert it back to String is like this...
Code:
`Dim MyString As String = new String(MyCharArray)`
You have spotted a mistake in my code v should be defined as Char, I've altered it.

You could use the above like this (the following assumes you wrap them in a Shared Class call Permutations)
vb Code:
`Dim MyString as String = "bcbedaefaa"Dim Sequence() as Char = MyString.ToCharArray() 'get the string into array form Permutations.ResetSequence(Sequence) 'alters the order to "aaabbcdeef" (perm 1)Do    'Do something with the sequence or with a string made from the sequence    'eg SomeFunctionThatAcceptsString(new String(Sequence))Loop While Permutations.Permute(Sequence) 'reorders the sequence to the next permutation`

There will be no memory issues because there only ever need be one string and one char array.

No VB.Net to test, might contain typos.

Edit: regarding Q1) it should not matter, you can associate the char values with whatever you want to, "Log", "Fruit", "Eye colour". They could be used as indexes for anything.  Reply With Quote

24. ## Re: recursive functions

ok; i got it..  Reply With Quote

#### Posting Permissions

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