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

Question

THI QUESTION CONTAINS VB.NET CODE BUT I CAN ACCEPT A SOLUTION EXPLAINED IN C#.

---

SCENARIO

---

In the past, and with some help from StackOverflow helper users, I built this function that makes permutations of characters:

<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

PROBLEM

---

Now, In C# or Vb.Net, I would like to permutate all the possible combinations between the elements of a collection (only a collection of numeric types, or strings).

This is what I have done so far, it is incomplete and is not returning me the expected results:

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

I need help to fix the resulting value that I'm getting, I'm getting collections of only two elements inside.

Is important for me to preserve the LINQ-to-Object approach.

C# online (and untested) translation:

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)
//=======================================================

EXPECTATIONS

---

If I pass an array to the function containing these elements: {10, 2, 30} then it should return me an IEnumerable(Of IEnumerable(Of Integer)) containing these collections:

• Item 1: {2, 10, 30}
• Item 2: {2, 30, 10}
• Item 3: {10, 2, 30}
• Item 4: {10, 30, 2}
• Item 5: {30, 10, 2}
• Item 6: {30, 2, 10}

If I pass an array to the function containing these elements: {"abc", "", "abc"} then it should return me an IEnumerable(Of IEnumerable(Of String)) containing these collections:

• Item 1: { "", "abc", "abc"}
• Item 2: {"abc", "", "abc"}
• Item 3: {"abc", "abc", ""}

The elements can be equals, the collections not.

The order matters, but I understand that is a different question, and I think that I can solve that by myself with LINQ grouping or sorting.

Answer 1

This works for me:

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());
    }
}

With var source = new[] { 10, 2, 30 }; I get:

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

And with var source = new[] { "abc", "", "abc" }; I get:

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

---

Vb.Net equivalent:

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

Take a look at Combinatorics - a nuget package (and source code) for computing permutations and combinations.

Answer 3

Not sure about performance. But compact

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