Link to home
Start Free TrialLog in
Avatar of DrDamnit
DrDamnitFlag for United States of America

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.

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.
ASKER CERTIFIED SOLUTION
Avatar of Mike Tomlinson
Mike Tomlinson
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of DrDamnit

ASKER

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

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