vb .net permutation of string. permutation or combination?
Solution 1:
Add this class to your project:
Public NotInheritable Class Permutation
Public Shared Function Create(array As Char()) As List(Of String)
Return Permutation.Create(array, False)
End Function
Public Shared Function Create(array As Char(), sort As Boolean) As List(Of String)
If (array Is Nothing) Then
Throw New ArgumentNullException("array")
ElseIf ((array.Length < 0) OrElse (array.Length > 13)) Then
Throw New ArgumentOutOfRangeException("array")
End If
Dim list As New List(Of String)
Dim n As Integer = array.Length
Permutation.Permute(list, array, 0, array.Length)
If (sort) Then
list.Sort()
End If
Return list
End Function
Private Shared Sub Permute(list As List(Of String), array As Char(), start As Integer, n As Integer)
Permutation.Print(list, array, n)
If (start < n) Then
Dim i, j As Integer
For i = (n - 2) To start Step -1
For j = (i + 1) To (n - 1)
Permutation.Swap(array, i, j)
Permutation.Permute(list, array, (i + 1), n)
Next
Permutation.RotateLeft(array, i, n)
Next
End If
End Sub
Private Shared Sub Print(list As List(Of String), array As Char(), size As Integer)
If (array.Length <> 0) Then
Dim s As Char() = New Char(size - 1) {}
For i As Integer = 0 To (size - 1)
s(i) = array(i)
Next
list.Add(s)
End If
End Sub
Private Shared Sub RotateLeft(array As Char(), start As Integer, n As Integer)
Dim tmp As Char = array(start)
For i As Integer = start To (n - 2)
array(i) = array(i + 1)
Next
array(n - 1) = tmp
End Sub
Private Shared Sub Swap(array As Char(), i As Integer, j As Integer)
Dim tmp As Char
tmp = array(i)
array(i) = array(j)
array(j) = tmp
End Sub
End Class
Because of the Int32.MaxValue
limit this class will support levels 1 through 13.
s=1, n=1
s=2, n=2
s=3, n=6
s=4, n=24
s=5, n=120
s=6, n=720
s=7, n=5040
s=8, n=40320
s=9, n=362880
s=10, n=3628800
s=11, n=39916800
s=12, n=479001600
s=13, n=6227020800
Usage:
Me.TextBox1.Text = String.Join(Environment.NewLine, Permutation.Create({"c"c, "f"c, "a"c, "m"c}, sort:=False))
Output:
cfam
cfma
cafm
camf
cmfa
cmaf
fcam
fcma
facm
famc
fmca
fmac
acfm
acmf
afcm
afmc
amcf
amfc
mcfa
mcaf
mfca
mfac
macf
mafc
The class is based on C++
code from the following link:
Calculating Permutations and Job Interview Questions
Solution 2:
This seems to be a Combination problem rather than Permutation :
"In mathematics, a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter". [Wikipedia]
Try to solve this by doing Combination to all item in array except the last item. Or in other words, do Combination operations nCk for all k, with
- n = size of input array minus the last item
- k = size of the output itemset, minimum k is 1 and maximum is n
Then append each Combination result with the last item. Following is the pseudocode code, using C# syntax :p
var input = new char[] {'C', 'F', 'A', 'M'};
//save last char
var lastChar = input[input.Length - 1];
//combinationInput is input member without the last character
var combinationInput = new char[input.Length - 1];
Array.Copy(input, 0, combinationInput, 0, combinationInput.Length);
//generate output with itemset size 1 to combinationInput.Length
for (int i = 1; i <= combinationInput.Length; i++)
{
//generate combination with size i
var combinationOutput = combinationInput.Combinations(i);
foreach (var combinedChar in combinationOutput)
{
//print output as: combinationOutput item + lastChar
Console.WriteLine(string.Join(", ", combinedChar) + ", " + lastChar);
}
}
References :
-
Array.Copy(...)
. [How to copy part of an array to another array] -
.Combinations(int outputSize)
extension method. [How to Generate Combinations of Elements of a List in .NET 4.0]