Here is a permutation class. I didn't create it, so if you are the
author or know who the author is, please take credit for it. I've only
made some minor tweaks to it. Someone emailed me yesterday asking about
password and uniqueness, so I sent him this little class to permutate a
string. Beware, large strings are very slow and take an enormous amount
of memory, as you'll see in the second code block that shows how to use
this class. Also, this class doesn't take into consideration that
letters may repeat. The permuation only uses each character once
in any given combination. Have fun!
Update: I've been asked if I have this
in C#. No, but it would
only take you 10 minutes or so to convert it. There are even some
websites out there that will do it for you with some minor tweaking
required on your part. If you're really
lazy, yes, I'll convert it and email it to you. Just leave a comment or
contact me using the contact link at the top of my blog page.
Public Class Permutation
Public Function Permutations(ByVal data As String) As String(,)
Dim i As Int32
Dim y As Int32
Dim x As Int32
Dim tempChar As String
Dim newString As String
Dim strings(,) As String
Dim rowCount As Int32
If data.Length < 2 Then
Exit Function
End If
'use the factorial function to determine the number of rows needed
'because redim preserve is slow
ReDim strings(data.Length - 1, Factorial(data.Length - 1) - 1)
strings(0, 0) = data
'swap each character(I) from the second postion to the second to last position
For i = 1 To (data.Length - 2)
'for each of the already created numbers
For y = 0 To rowCount
'do swaps for the character(I) with each of the characters to the right
For x = data.Length To i + 2 Step -1
tempChar = strings(0, y).Substring(i, 1)
newString = strings(0, y)
Mid(newString, i + 1, 1) = newString.Substring(x - 1, 1)
Mid(newString, x, 1) = tempChar
rowCount = rowCount + 1
strings(0, rowCount) = newString
Next
Next
Next
'Shift Characters
'for each empty column
For i = 1 To data.Length - 1
'move the shift character over one
For x = 0 To strings.GetUpperBound(1)
strings(i, x) = strings(i - 1, x)
Mid(strings(i, x), i, 1) = strings(i - 1, x).Substring(i, 1)
Mid(strings(i, x), i + 1, 1) = strings(i - 1, x).Substring(i - 1, 1)
Next
Next
Return strings
End Function
Public Function Factorial(ByVal Number As Integer) As Int32
Try
If Number = 0 Then
Return 1
Else
Return Number * Factorial(Number - 1)
End If
Catch ex As Exception
Throw
End Try
End Function
End Class
Here
are a few examples that have been commented out, except the first and
fastest one. Note how much longer it takes and the memory requirements
after the array reaches a certain size.
Private Sub TestPerm()
Button1.Enabled = False
Console.WriteLine("Starting")
Console.WriteLine(DateTime.Now().ToString & DateTime.Now.Millisecond.ToString())
Dim p As Permutation = New Permutation
' 3 gen2 GCs
' 450,686 bytes total allocations across 5,673 instances
' 16 ms max execution time
' 120 permutations
Dim a As String(,) = p.Permutations("abcde")
' 3 gen2 GCs
' 540,000 bytes total allocations across 9,366 instances
' 15 ms max execution time
' 720 permutations
'Dim a As String(,) = p.Permutations("abcdef")
' 4 gen2 GCs
' 1,182,484 bytes total allocations across 35,293 instances
' 16 ms max execution time
' 5,040 permutations
'Dim a As String(,) = p.Permutations("abcdefg")
' 4 gen2 GCs
' 1,182,484 bytes total allocations across 35,293 instances
' 94 ms max execution time
' 40,320 permutations
'Dim a As String(,) = p.Permutations("abcdefgh")
' Didn't allow to complete - killed after 240 secs in CLR Profiler
' 33 gen2 GCs
' 294,390,632 bytes total allocations across 10,751,199 instances
' 8 secs max execution time
' 3,628,800 permutations
'Dim a As String(,) = p.Permutations("abcdefghij")
Console.WriteLine("Permutation array complete")
Console.WriteLine(DateTime.Now().ToString & DateTime.Now.Millisecond.ToString())
Dim myEnumerator As System.Collections.IEnumerator = a.GetEnumerator()
Dim i As Int32 = 0
Dim count As Int32 = 0
Dim cols As Int32 = a.GetLength(a.Rank - 1)
While myEnumerator.MoveNext()
If i < cols Then
i += 1
Else
i = 1
End If
count += 1
'Console.WriteLine(myEnumerator.Current.ToString())
End While
Console.WriteLine(count)
Console.WriteLine(DateTime.Now().ToString & DateTime.Now.Millisecond.ToString())
Console.WriteLine("Finished")
Console.WriteLine()
Button1.Enabled = True
End Sub
Currently listening to:45 - Shinedown
Posted
03-01-2005 7:42 AM
by
Raymond Lewallen