vb .net permutation of string. permutation or combination?

Question

i've got arary of string like this C - F - A - M. i want to create a combination from that with condition:

1. each other item beside last character has to be combined with last character

2. there's not allowed a same combination, even the order is different. for example

   FC - M

   CF - M

3. if the string array contains >=3 element it will generate 2 & 3 itemset, if 2 element then it will generate only 2 itemset

below is my code. my code generate the result like right part of the picture

my question is what method should i use? is it permutation, combination, or other things? and in pseudocode, what is my case would be like?

here's my code

Public Class permute
Dim ItemUsed() As Boolean
Dim pno As Long, pString As String
Dim inChars() As Char = {"c", "f", "a", "m"}

Private Sub permute_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load  
End Sub

Sub Permute(ByVal K As Long)
    ReDim ItemUsed(K)
    pno = 0

    Dim i As Integer
    For i = 2 To K
        Permutate(i, 1)
        tb.Text = K
    Next
End Sub

Private Sub Permutate(ByVal K As Long, ByVal pLevel As Long)
    Dim i As Long, Perm As String
    Perm = pString

    For i = 0 To K - 1
        If Not ItemUsed(i) Then
            If pLevel = 1 Then
                pString = inChars(i)
            Else
                pString += inChars(i)
            End If
            If pLevel = K Then
                pno = pno + 1
                Results.Text += _
                pno & " " & " = " & " " & pString & vbCrLf
                Exit Sub
            End If

            ItemUsed(i) = True
            Permutate(K, pLevel + 1)
            ItemUsed(i) = False
            pString = Perm
        End If
    Next
End Sub

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    Permute(tb.Text)
End Sub

Private Sub tb_TextChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles tb.TextChanged
    If tb.Text = "" Then
        Results.Text = ""
    Else
        Permute(tb.Text)
    End If
End Sub
End Class

here's the requirement screenshot

and here's the program screenshot

Answer 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

Answer 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 :

1. Array.Copy(...). [How to copy part of an array to another array]
2. .Combinations(int outputSize) extension method. [How to Generate Combinations of Elements of a List in .NET 4.0]