LINQ for generating all possible permutations
English language

These are relatively minor issues, but fixing them might help other people to use / maintain your code.


The verb corresponding to permutation is permute.
I'm pretty sure that reminder is intended as remainder.


Code


    public static IEnumerable&lt;T[]&gt; Permutate&lt;T&gt;(this IEnumerable&lt;T&gt; source)
    {
        return permutate(source, Enumerable.Empty&lt;T&gt;());
        IEnumerable&lt;T[]&gt; permutate(IEnumerable&lt;T&gt; reminder, IEnumerable&lt;T&gt; prefix) =&gt;
            !reminder.Any() ? new[] { prefix.ToArray() } :
            reminder.SelectMany((c, i) =&gt; permutate(
                reminder.Take(i).Concat(reminder.Skip(i+1)).ToArray(),
                prefix.Append(c)));
    }



To return a permutation of source it is necessary to find all of the elements of source, so I think this is a case where the first thing the method should do is to fully evaluate source (e.g. with ToList() or ToArray()), and then work with that list rather than source. Apart from the efficiency benefits, that guarantees that all of the permutations will be permutations of the same size and elements, even if source has side-effects.

There are a couple of things you can then do with a list to make it much more efficient. Either you can use a standard "next permutation" algorithm (see Wikipedia: for arbitrary inputs it can be done by permuting an array of integers and copying the operations on the array of T) or you can recursively select an element from the first k, swap it to position k, recurse on k-1, and then swap it back. When k==0 you instead copy the entire array and yield the copy. This avoids building up chains of Append and the overheads of Take/Skip/Concat. I expect that the most efficient would be the "next permutation" approach, because it is non-recursive and so doesn't wrap coroutine in coroutine.