.net - 修复此生成空字符串的排列生成器函数

Question

我在@Artur Udod 上回答了这个问题:

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

我修改了代码以返回字符串而不是 Char 的集合，并且还能够指定在生成的排列中是否允许字符重复:

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

用法示例:

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

问题是，当我将重复设置为 False 时，该函数将创建、解析并返回空字符串，性能的负面影响会导致较大的集合或排列长度。

我知道我可以使用 IEnumerable.Distinct() 方法删除除一个以外的所有空字符串，但这会再次迭代整个大集合，从而对代码本身造成更多的负面影响。

我如何才能高效且正确地设计函数，同时考虑性能以及创建排列集合所需的总体执行时间？

重要的是，我不认为使用 LINQ 会降低性能，我会继续使用 LINQ，因为它允许开发精简的代码而不是像这样翻译 LINQ 查询所需的数千行普通循环。

PS:我的次要目标是在函数上实现 Iterator 关键字以进一步提高其性能，如果有人可以用解决方案来说明这个问题，同时实现 Iterator 功能，那就太棒了(和完美)。

Answer 1

我认为您不应该从 linq 开始，因为您似乎还没有掌握它。也许尝试更简单的构造:

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

使用这个包装器调用它，我们在其中设置列表并检查合理的参数:

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