Fix this permutation generator function that generates empty strings

Question

I've taken a permutation generator solution on @Artur Udod answer in this question:

Print all the possible combinations of "X" amount of characters with "X" string length (Brute Force)

I've adapted the code to return Strings instead a collection of Char andalso be able to specify whether character repetition is allowed or not on the generated permutations:

Public Shared Function PermuteCharacters(ByVal charSet As IEnumerable(Of Char),
                                         ByVal length As Integer,
                                         ByVal isRepetitionAllowed As Boolean) As IEnumerable(Of String)

    If length = 1 Then
        Return charSet.Select(Function(c As Char)
                                  Return New String(New Char() {c})
                              End Function)

    Else
        Return PermuteCharacters(charSet, length - 1, isRepetitionAllowed).
               SelectMany(Function(x As String) charSet,
                          Function(str As String, c As Char)

                              Select Case isRepetitionAllowed

                                  Case True
                                      Return str & c

                                  Case Else
                                      ' Firstly I need to check if string is empty because 
                                      ' String.Contains() will throw an exception on empty strings.
                                      ' This need to be fixed to avoid empty strings.
                                      If String.IsNullOrEmpty(str) Then
                                          Return Nothing
                                      End If

                                      If Not str.Contains(c) Then
                                          Return str & c
                                      Else
                                          Return Nothing
                                      End If

                              End Select

                          End Function)

    End If

End Function

An example usage:

Dim permutations As IEnumerable(Of String) =
    PermuteCharacters("123456789", 2, isRepetitionAllowed:=False)

The problem is that the function will create, parse, and return empty strings when I set repetition to False, with the negative point of performance that will cause in large set or permutation lengths.

I know that I could use IEnumerable.Distinct() method to remove all empty strings but one, but that will iterate again the entire big collection causing more negative performance on the code itself.

How can I design efficiently and properly the function, taking in count the performance, the overall execution time needed to create a collection of permutations?.

Its important to say that I don't see LINQ usage as a very disadvantage of performance, I will to keep using LINQ because it allows to develop a reduced code instead of the required thousands of lines for a common Loop to translate a LINQ query like that.

PS: My secondary goal is to implement the Iterator keyword on the function to improve more its performance, if someone could illustrate with a solution for this issue that also implements the Iterator capabilities will be more than awesome (and perfect).

Answer 1

I don't think you should start with linq since it doesn't look like you master it already. Perhaps try a simpler construct:

Private Shared Iterator Function BuildCombination(distinctChars As IEnumerable(Of Char), usedChars As Stack(Of Char), length As Integer, everyCharIsDistinct As Boolean) As IEnumerable(Of String)
' we give the method everything it needs to work
    Dim availableChars As IEnumerable(Of Char) = distinctChars
    ' what chars are available
    If everyCharIsDistinct Then
        availableChars = availableChars.Where(Function(c As Char) Not usedChars.Contains(c))
    End If
    ' if the string to return is of length 1, every available char can be returned directly
    If length = 1 Then
        For Each availableChar As Char In availableChars
            Yield New String(New Char()() = { availableChar })
        Next
    Else
        ' else we add each available char to the used list and we recurse to concat it with every possible substring
        For Each availableChar As Char In availableChars
            usedChars.Push(availableChar)
            For Each possibleSubstring As String In Program.BuildCombination(distinctChars, usedChars, length - 1, everyCharIsDistinct)
                Yield New String(New Char()() = { availableChar }) + possibleSubstring 
            Next
            usedChars.Pop()
        Next
    End If
    Return
End Function

Call it using this wrapper where we setup the lists and where we check for sane parameters:

Private Shared Sub FindCombinations(possibleChars As String, length As Integer, everyCharIsDistinct As Boolean)
    If possibleChars.Length = 0 Then
        Throw New InvalidOperationException()
    End If
    If everyCharIsDistinct AndAlso possibleChars.Length < length Then
        Throw New InvalidOperationException()
    End If
    Dim distinctChars As IEnumerable(Of Char) = possibleChars.Distinct(Of Char)()
    Dim listOfUsedChars As Stack(Of Char) = New Stack(Of Char)()
    For Each s As String In Program.BuildCombination(distinctChars, listOfUsedChars, length, everyCharIsDistinct).ToList(Of String)()
        Console.WriteLine(s)
    Next
End Sub