DrDamnit
asked on
Recursive Word Builder?
I am trying to build an application that will read a pattern and build "words" from two arrays. One array is full of consonants, and one array is full of vowels.
I need to figure out how to create a function (maybe a recursive one?) where I can pass it a pattern like: "CVCV" and it will look through these letters and create every possible combination from the arrays that matches the pattern.
Some example words for CVCV (consonant-vowel-consonant -vowel):
LANI
CAMA
DIPO
If we pass it this pattern: CVV, it would create words like:
LEI
RAO
TIE
How do I structure this function? I am having trouble with the logic and structure.
Dim aryConsonants As String() = {"b", "d", "f", "g", "k", "l", "m", "p", "r", "s", "t", "v", "w", "x", "z"}
Dim aryVowels As String() = {"a", "e", "i", "o", "u"}
I need to figure out how to create a function (maybe a recursive one?) where I can pass it a pattern like: "CVCV" and it will look through these letters and create every possible combination from the arrays that matches the pattern.
Some example words for CVCV (consonant-vowel-consonant
LANI
CAMA
DIPO
If we pass it this pattern: CVV, it would create words like:
LEI
RAO
TIE
How do I structure this function? I am having trouble with the logic and structure.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
You're using background workers, so F8 Steps aren't helping me watch the process. Can you teach me what the concept is behind this? The code is quite elegant. I know what it's doing, but don't know how / why.
I'm not quite sure how to explain it...describing how a recursive algorithm works is always tricky. =\
How do you plan on using this? After more than five characters (approx) in the pattern, the running time is going to get quite long and the return set is going to get huge.
How do you plan on using this? After more than five characters (approx) in the pattern, the running time is going to get quite long and the return set is going to get huge.
Here's a more compact version:
Public Class Form1
Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
Dim aryVowels As String() = {"a", "e", "i", "o", "u"}
Dim aryConsonants As String() = {"b", "c", "d", "f", "g", "h", "j", "k", "l", "m", "n", "p", "q", "r", "s", "t", "v", "w", "x", "y", "z"}
For Each vowel As String In aryVowels
Dim ltr As New Letter
ltr.Value = vowel
ltr.Type = Letter.LetterType.Vowel
Letter.Letters.Add(ltr)
Next
For Each consonant As String In aryConsonants
Dim ltr As New Letter
ltr.Value = consonant
ltr.Type = Letter.LetterType.Consonant
Letter.Letters.Add(ltr)
Next
End Sub
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
ListBox1.DataSource = Nothing
ListBox1.Items.Clear()
Button1.Enabled = False
BackgroundWorker1.RunWorkerAsync(TextBox1.Text)
End Sub
Private Sub BackgroundWorker1_DoWork(sender As Object, e As System.ComponentModel.DoWorkEventArgs) Handles BackgroundWorker1.DoWork
Dim pattern As String = e.Argument.ToString.Trim.ToUpper
Dim words As Dictionary(Of String, Object) = Nothing
If pattern.Replace("C", "").Replace("V", "") = "" Then
words = New Dictionary(Of String, Object)
For Each ltr As Letter In Letter.Letters
ltr.Visit(pattern, 0, "", words)
Next
End If
e.Result = words.Keys.ToList
End Sub
Private Sub BackgroundWorker1_RunWorkerCompleted(sender As Object, e As System.ComponentModel.RunWorkerCompletedEventArgs) Handles BackgroundWorker1.RunWorkerCompleted
If Not IsNothing(e.Result) Then
Dim words As List(Of String) = DirectCast(e.Result, List(Of String))
ListBox1.DataSource = words
MessageBox.Show("Done!")
Else
MessageBox.Show("Invalid Pattern")
End If
Button1.Enabled = True
End Sub
Public Class Letter
Public Enum LetterType
Vowel
Consonant
End Enum
Public Value As String
Public Type As LetterType
Public Shared Letters As New List(Of Letter)
Public Sub Visit(ByVal pattern As String, ByVal patternPosition As Integer, ByVal word As String, ByVal words As Dictionary(Of String, Object))
Dim Code As String = pattern.Substring(patternPosition, 1)
If (Code = "V" AndAlso Me.Type = LetterType.Vowel) OrElse (Code = "C" AndAlso Me.Type = LetterType.Consonant) Then
word = word & Me.Value
If word.Length = pattern.Length Then
If Not words.ContainsKey(word) Then
words.Add(word, Nothing)
End If
Else
For Each ltr As Letter In Letter.Letters
ltr.Visit(pattern, patternPosition + 1, word, words)
Next
End If
End If
End Sub
End Class
End Class
ASKER
This was great. To learn what you did, I built a different, yet similar program to do something else entirely different, and I think I have figured about half of it out.
The one bit I cannot figure out is how you are rotating based on the pattern like an odometer...
The one bit I cannot figure out is how you are rotating based on the pattern like an odometer...
In my last post, lines 72 thru 74 are what allows it to recursively iterate through all the letters and see if they fit the pattern in the next available slot.
ASKER
I will be F8 - stepping through this until I figure out how / why it works. GREATLY appreciated.