## Generating PermutationsThe 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). ## ListingThe 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 |