使用 LINQ 排列集合元素的所有可能组合

Question

问题包含 VB.NET 代码，但我可以接受用 C# 解释的解决方案。

场景

过去，在 Whosebug 帮助用户的帮助下，我构建了这个进行字符排列的函数：

<DebuggerStepThrough>
Public Shared Function PermuteCharacters(ByVal charSet As IEnumerable(Of Char),
                                         ByVal length As Integer,
                                         ByVal allowRepetition As Boolean) As IEnumerable(Of String)

    If (charSet.Count <> charSet.Distinct.Count) Then
        Throw New ArgumentException("Char-set contains duplicated characters.", "charSet")
        Return Nothing
    End If

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

    If (allowRepetition) Then
        Return PermuteCharacters(charSet:=charSet, length:=length - 1, allowRepetition:=True).
               SelectMany(Function(str As String)
                              Return charSet
                          End Function,
                          Function(str As String, c As Char)
                              Return str & c
                          End Function)

    Else
        Return PermuteCharacters(charSet:=charSet, length:=length - 1, allowRepetition:=False).
           SelectMany(Function(x As String) charSet,
                      Function(str As String, c As Char)
                          If Not str.Contains(c) Then
                              Return str & c
                          Else
                              Return Nothing
                          End If
                      End Function).
        Where(Function(value As String) value IsNot Nothing)

    End If

End Function

问题

现在，在 C# 或 Vb.Net 中，我想排列集合元素之间的所有可能组合（仅数字类型或字符串的集合）。

这是我到目前为止所做的，它是不完整的并且没有 return 给我预期的结果：

Public Shared Function PermuteItems(ByVal items As IEnumerable(Of String)) As IEnumerable(Of IEnumerable(Of String))

    Return items.SelectMany(
        Function(x As String) As IEnumerable(Of String)
            Return items
        End Function,
        Function(str1 As String, str2 As String) As IEnumerable(Of String)
            Return {str1}.Concat({str2})
        End Function)

End Function

Public Shared Function PermuteItems(ByVal items As IEnumerable(Of Integer)) As IEnumerable(Of IEnumerable(Of String))

    Return PermuteItems((From item As Integer In items Select Convert.ToString(item)))

End Function

我需要帮助来修复我得到的结果值，我得到的是内部只有两个元素的集合。

对我来说保留 LINQ-to-Object 方法很重要。

C# 在线（未经测试）翻译：

public static IEnumerable<IEnumerable<string>> PermuteItems(IEnumerable<string> items) {
    return items.SelectMany((string x) => { return items; }, (string str1, string str2) => { return { str1 }.Concat({ str2 }); });
}

public static IEnumerable<IEnumerable<string>> PermuteItems(IEnumerable<int> items) {
    return PermuteItems((from item in itemsConvert.ToString(item)));
}

//=======================================================
//Service provided by Telerik (www.telerik.com)
//=======================================================

期望值

如果我将数组传递给包含这些元素的函数：{10, 2, 30} 那么它应该 return 我 IEnumerable(Of IEnumerable(Of Integer)) 包含这些合集：

项目 1：{2, 10, 30}
项目 2：{2, 30, 10}
项目 3：{10、2、30}
项目 4：{10、30、2}
项目 5：{30、10、2}
项目 6：{30、2、10}

如果我将数组传递给包含这些元素的函数：{"abc", "", "abc"} 那么它应该 return 我 IEnumerable(Of IEnumerable(Of String)) 包含这些集合：

项目 1：{ "", "abc", "abc"}
项目 2：{"abc", "", "abc"}
项目 3：{"abc"、"abc"、“”}

元素可以相等，集合不能。

顺序很重要，但我知道这是一个不同的问题，我认为我可以通过 LINQ 分组或排序自行解决。

Answer 1

这对我有用：

public IEnumerable<IEnumerable<T>> Permutate<T>(IEnumerable<T> source)
{
    var xs = source.ToArray();
    return
        xs.Length == 1
            ? new [] { xs }
            : (
                from n in Enumerable.Range(0, xs.Length)
                let cs = xs.Skip(n).Take(1)
                let dss = Permutate<T>(xs.Take(n).Concat(xs.Skip(n + 1)))
                from ds in dss
                select cs.Concat(ds)
            ).Distinct(new EnumerableEqualityComparer<T>());
}

private class EnumerableEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> a, IEnumerable<T> b)
    {
        return a.SequenceEqual(b);
    }

    public int GetHashCode(IEnumerable<T> t)
    {
        return t.Take(1).Aggregate(0, (a, x) => a ^ x.GetHashCode());
    }
}

使用 var source = new[] { 10, 2, 30 }; 我得到：

{10, 2, 30} 
{10, 30, 2} 
{2, 10, 30} 
{2, 30, 10} 
{30, 10, 2} 
{30, 2, 10}

然后 var source = new[] { "abc", "", "abc" }; 我得到：

{"abc", "", "abc"} 
{"abc", "abc", ""} 
{"", "abc", "abc"}

Vb.Net相当于：

Public Function Permutate(Of T)(source As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))

    Dim xs As T() = source.ToArray()

    Return If(xs.Length = 1,
              {xs},
              (From n In Enumerable.Range(0, xs.Length)
               Let cs = xs.Skip(n).Take(1)
               Let dss = Permutate(Of T)(xs.Take(n).Concat(xs.Skip(n + 1)))
               From ds In dss Select cs.Concat(ds))
              ).Distinct(New EnumerableEqualityComparer(Of T)())

End Function

Public Class EnumerableEqualityComparer(Of T) : Implements IEqualityComparer(Of IEnumerable(Of T))

    Public Shadows Function Equals(a As IEnumerable(Of T), b As IEnumerable(Of T)) As Boolean _
    Implements IEqualityComparer(Of IEnumerable(Of T)).Equals
        Return a.SequenceEqual(b)
    End Function

    Public Shadows Function GetHashCode(t As IEnumerable(Of T)) As Integer Implements _
    IEqualityComparer(Of IEnumerable(Of T)).GetHashCode
        Return t.Take(1).Aggregate(0, Function(a, x) a Xor x.GetHashCode())
    End Function

End Class

Answer 2

查看 Combinatorics - a nuget package (and source code) 以计算排列和组合。

Answer 3

不确定性能。但是紧凑

var permutation = list.SelectMany((item,i) => list.Skip(i + 1).Select((another) => (item, another)));

使用 LINQ 排列集合元素的所有可能组合

Permutate all possible combinations of the elements of a collection, using LINQ

.net

c#

linq

vb.net

permutation

场景

问题

期望值