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.

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"}

Open in new window


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.
LVL 32
DrDamnitAsked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
Mike TomlinsonConnect With a Mentor Middle School Assistant TeacherCommented:
Try this out:  *Form has a TextBox, Button, ListBox and a BackgroundWorker*
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.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
    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 Dictionary(Of String, Object) = DirectCast(e.Result, Dictionary(Of String, Object))
            ListBox1.BeginUpdate()
            ListBox1.Items.AddRange(words.Keys.ToArray)
            ListBox1.EndUpdate()
            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 Overrides Function ToString() As String
            Return Value
        End Function

        Public Sub Visit(ByVal pattern As String, ByVal patternPosition As Integer, ByVal word As String, ByVal words As Dictionary(Of String, Object))
            If patternPosition = pattern.Length Then
                If Not words.ContainsKey(word) Then
                    words.Add(word, Nothing)
                End If
            Else
                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
                    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

Open in new window

0
 
DrDamnitAuthor Commented:
Wow. Above and beyond man. Thank you very much.

I will be F8 - stepping through this until I figure out how / why it works. GREATLY appreciated.
0
 
DrDamnitAuthor Commented:
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.
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
Mike TomlinsonMiddle School Assistant TeacherCommented:
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.
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
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

Open in new window

0
 
DrDamnitAuthor Commented:
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...
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
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.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.