Excel Developer Tip

Excel page

Tip archives

Generating Permutations

The number of permutations of a string is equal to the factorial of the length of the string. For example, the word DOG has a length of three -- which means that the letters can be rearranged in six different ways: DOG, DGO, ODG OGD, GDO, and GOD. The number of permutations quickly gets unwieldy. The table below lists the number of permutations for strings of various sizes.

This tip describes how to generate all permutations from a string. It uses a recursive subroutine to do the work. The source of this algorithm is not known (I was browsing through some old files on my hard drive and discovered it).

• Download a file that demonstrates this technique

Listing

The GetString subroutine prompts the user for a string. If the length of the string is greater than 1 and less than 8, the GetPermutations subroutine is called --which then calls itself. The permutations are stored in column A of the worksheet.

Dim CurrentRow

Sub GetString()
    Dim InString As String
    InString = InputBox("Enter text to permute:")
    If Len(InString) < 2 Then Exit Sub
    If Len(InString) >= 8 Then
        MsgBox "Too many permutations!"
        Exit Sub
    Else
        ActiveSheet.Columns(1).Clear
        CurrentRow = 1
        Call GetPermutation("", InString)
    End If
End Sub

Sub GetPermutation(x As String, y As String)
'   The source of this algorithm is unknown
    Dim i As Integer, j As Integer
    j = Len(y)
    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
End Sub