Get all combinations of recursive substring replacement

Posted on 2012-08-30
Last Modified: 2012-09-05
I'm looking for a way to replace a substring within a string, and obtaining all different combinations, for example:

"one leg two legs", and replacing "leg" with "arm" it would return the following strings:

"one leg two legs"
"one arm two legs"
"one leg two arms"
"one arm two arms"

I have made a quite simple routine for this but it fails when replacing "i" with "ie" (infinite recursion because string builds up, pie > piee > pieee > pieeee) and if i fix that by recursing backwards if tails when replacing for example "ch" with "sch" (michael > mischael > misschael > missschael) - im just stuck as hell and trying all night - please help?
Question by:MisterMiyagi
    LVL 37

    Expert Comment

    When you replace a string, advance the pointer the length of the string you just replaced with.

    What functions are you using? Find? The parameter for find that tells where to start the search would be the pointer. So just increment that by WordYouJustAdded.Length
    LVL 85

    Accepted Solution

    Try something like this out:
    Public Class Form1
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Dim data As String = "one leg two legs three leg eight legs"
            Dim find As String = "leg"
            Dim replace As String = "arm"
            Dim values() As String = data.Split(New String() {find}, StringSplitOptions.None)
            Dim combos As Integer = Math.Pow(2, values.Length - 1)
            Dim binary As String
            Dim maxWidth As Integer = Convert.ToString(combos - 1, 2).Length
            Dim combination As New System.Text.StringBuilder
            For i As Integer = 0 To combos - 1
                binary = Convert.ToString(i, 2).PadLeft(maxWidth, "0")
                For j = 0 To values.Length - 2
                    combination.Append(values(j) & IIf(binary.Substring(j, 1) = "0", find, replace))
        End Sub
    End Class

    Open in new window

    Which produced the following output:
    one leg two legs three leg eight legs
    one leg two legs three leg eight arms
    one leg two legs three arm eight legs
    one leg two legs three arm eight arms
    one leg two arms three leg eight legs
    one leg two arms three leg eight arms
    one leg two arms three arm eight legs
    one leg two arms three arm eight arms
    one arm two legs three leg eight legs
    one arm two legs three leg eight arms
    one arm two legs three arm eight legs
    one arm two legs three arm eight arms
    one arm two arms three leg eight legs
    one arm two arms three leg eight arms
    one arm two arms three arm eight legs
    one arm two arms three arm eight arms

    Author Closing Comment

    Thx mate!

    Author Comment

    Thank you TommySzalapski! Im sure your code would have worked too, however I preferred the second one since it didnt use recursing (brute) but mathematically found all combinations (finesse), thanks a lot for your help though!

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    What Should I Do With This Threat Intelligence?

    Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

    This article describes relatively difficult and non-obvious issues that are likely to arise when creating COM class in Visual Studio and deploying it by professional MSI-authoring tools. It is assumed that the reader is already familiar with the cla…
    Many of us here at EE write code. Many of us write exceptional code; just as many of us write exception-prone code. As we all should know, exceptions are a mechanism for handling errors which are typically out of our control. From database errors, t…
    Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…
    Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    22 Experts available now in Live!

    Get 1:1 Help Now