recursive functions

[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..

[dbasnett]

Is this what you want?

        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

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

[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..

[cem babaeren]

also output is what i really want..

[dbasnett]

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 ?.

[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..

[BlindSniper]

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.

  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()
        ' Start with the all one-letter combinations.
        newStrings.AddRange(characters)

        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.
                    newStrings.Add(str & ch)
                    Console.WriteLine(str & ch)
                Next
            Next
        Next

[dbasnett]

isn't it clear? it would be any number..

It was there, that is clear.

[techgnome]

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

[cicatrix]

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

''' <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:

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:

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;

[cicatrix]

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

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:

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

[cem babaeren]

thanks to all;

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

[BlindSniper]

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.

[cicatrix]

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.

[cem babaeren]

dear blindsniper; i tried yours first:

i am putting what i have done with your reply below:

       
        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()
       
        newStrings.AddRange(characters)
        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
                    newStrings.Add(temp_str)
                    temp_str_splitted = Split(temp_str, ";")
                    If UBound(temp_str_splitted) + 1 = 4 Then
                        count += 1
                        ListBox1.Items.Add(temp_str)
                    End If

                    Console.WriteLine(str & ch)
                Next
            Next
        Next
        ListBox1.Items.Add(count)

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?

thanks for your help;

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

[cem babaeren]

dear cicatrix;

i couldn't have successed to adopt your code.

My final code is the below:

    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
            value_list.Add(temp_value) '(1, 4, 7, 10)
            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
            newStrings.Add(value_list(i))
        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
                    newStrings.Add(temp_str)
                    temp_str_splitted = Split(temp_str, ";")
                    If UBound(temp_str_splitted) + 1 = number_of_variables Then
                        count += 1
                        combination_list.Add(temp_str)
                    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..

[Milk]

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.

[cem babaeren]

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..

[Milk]

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.

[cem babaeren]

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..

[Milk]

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().

	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.

[cem babaeren]

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

i had a quick search at your code.

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..

[Milk]

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...

Dim MyCharArray() As Char = "bananas".ToCharArray()

One way to convert it back to String is like this...

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)

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.

[cem babaeren]

ok; i got it..