HOW TO: Get a list of all permutations of a string

Recently, I was working with my boss to interview new developers and he asked me for a trick on how to analyze the level of skill that a coder had. I applied for a position at a job when I was just starting out as a developer and was asked a very simple question, which turned out to be very difficult to interpret into code. He asked me how would I find every permutation of a string without duplicate values.

It seems very simple, but for a developer to interpret that into code takes some time and understanding of how everything is interpreted in software.

Here is a sample snippet of code to achieve this:

Sub Main()
        Dim strInputString As String = String.Empty
        Dim lstPermutations As List(Of String)
        'Loop until exit character is read
        While strInputString <> "x"
            Console.Write("Please enter a string or x to exit: ")
            strInputString = Console.ReadLine()
            If strInputString = "x" Then
                Continue While
            End If
            'Create a new list and append all possible permutations to it.
            lstPermutations = New List(Of String)
            Append(strInputString, lstPermutations)

            'Sort and display list+stats
            lstPermutations.Sort()
            For Each strPermutation As String In lstPermutations
                Console.WriteLine("Permutation: " + strPermutation)
            Next
            Console.WriteLine("Total: " + lstPermutations.Count.ToString)
            Console.WriteLine("")
        End While
    End Sub

    Public Sub Append(ByVal pString As String, ByRef pList As List(Of String))
        Dim strInsertValue As String
        Dim strBase As String
        Dim strComposed As String
        'Add the base string to the list if it doesn't exist

        If pList.Contains(pString) = False Then
            pList.Add(pString)
        End If
        'Iterate through every possible set of characters
        For intLoop As Integer = 1 To pString.Length - 1
            'we need to slide and call an interative function.
            For intInnerLoop As Integer = 0 To pString.Length - intLoop
                'Get a base insert value, example (a,ab,abc)
                strInsertValue = pString.Substring(intInnerLoop, intLoop)
                'Remove the base insert value from the string eg (bcd,cd,d)
                strBase = pString.Remove(intInnerLoop, intLoop)
                'insert the value from the string into spot and check
                For intCharLoop As Integer = 0 To strBase.Length - 1
                    strComposed = strBase.Insert(intCharLoop, strInsertValue)
                    If pList.Contains(strComposed) = False Then
                        pList.Add(strComposed)
                        'Call the same function to review any sub-permutations.
                        Append(strComposed, pList)
                    End If
                Next
            Next
        Next
End Sub

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>