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

Question

我在@Artur Udod 上采用了排列生成器解决方案，回答这个问题：

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

我已将代码改编为 return 字符串，而不是 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 时，该函数将创建、解析和 return 空字符串，性能的负面影响会导致在大集合或排列长度中。

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

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

重要的是我不认为 LINQ 的使用是性能的一个非常不利的地方，我将继续使用 LINQ因为它允许开发一个精简的代码，而不是需要数千行的普通 Loop 来翻译这样的 LINQ 查询。

PS：我的次要目标是在函数上实现 Iterator 关键字以提高其性能，如果有人可以针对此问题提供解决方案来说明也实现了 [=14] =] 能力将不仅仅是令人敬畏的（和完美的）。

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

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

Fix this permutation generator function that generates empty strings

.net

vb.net

algorithm

combinations

permutation