Permutation function in C#

One thing lead to another and eventually I wanted to know the "proper" way of writing the permutation generating function in C#. Below is my code for generating permutations. This will go into an internal library, so the calling context is really generic. Expected calling is in a single-threaded context

/// 
/// Generate all possible permutations of all elements in the list taken r at a time
/// Permutations: Choose 'r' letters from 'n' possible letters to form a word (sequence is important). 
/// Formula for counting: nPr = n! / (n - r)!
/// 
/// The list whose permutations are needed
/// The position of first element of interest in the list
/// Number of items required in the permuted list
/// An enumeration containing a permutation of the original list
public static IEnumerable> GetPermutations(this IList list, int r, int startPos = 0) {
    for (int i = startPos; i  1) {
            list.Swap(startPos, i);
            foreach (var permute in GetPermutations(list, r - 1, startPos + 1))
                yield return new List().AddRange(list[startPos].AsEnumerable(), permute);
            list.Swap(startPos, i);
        } else
            yield return new List() { list[i] };
    }
}

The Utils class has the extensions used in the GetPermutations function

public static class Utils {
    public static bool Swap(this IList list, int i1, int i2) {
        if (i1 == i2)
            return false;
        var tmp = list[i1];
        list[i1] = list[i2];
        list[i2] = tmp;
        return true;
    }

    public static IEnumerable AsEnumerable(this T item) {
        yield return item;
    }

    public static List AddRange(this List list, params IEnumerable[] collections) {
        foreach (var collection in collections)
            list.AddRange(collection);
        return list;
    }

}

The code will be invoked as below

```
var items = new [] { 'a', 'b', 'c', 'd'};
foreach (var permutation in items.GetPermutations(3))
Console.WriteLine(string.J

To answer your (1) yield return in a recursive method ... Eric Lippert does it in Producing Permutations series, Part Three , specifically in his HamiltonianPermutationsIterator recursive method.

I won't dive into your (2) only to suggest that perhaps you read all of Eric Lippert's series to learn more.

Braces Need Improving

On coding style, your use (or lack thereof) of braces could be improved. The C# convention is to put the opening brace on a new line (this differs from Java).

More importantly is that you lack braces on so many one-liners. This is heavily discouraged.

I would suggest cleaning your code to change a snippet from this:

if (r > 1) {
    list.Swap(startPos, i);
    foreach (var permute in GetPermutations(list, r - 1, startPos + 1))
        yield return new List().AddRange(list[startPos].AsEnumerable(), permute);
    list.Swap(startPos, i);
} else
    yield return new List() { list[i] };

To this:

if (r > 1) 
{
    list.Swap(startPos, i);
    foreach (var permute in GetPermutations(list, r - 1, startPos + 1))
    {
        yield return new List().AddRange(list[startPos].AsEnumerable(), permute);
    }
    list.Swap(startPos, i);
} 
else
{
    yield return new List() { list[i] };
}

Swap Method

You really don't do anything with the bool returned from the Swap method. Plus I see little reasoning in not swapping 2 values that happen to be equal. This method could simply be void.

You are also encouraged to have meaningful names in C#, so i1 would be better named as index1. Ditto for i2.

public static void Swap(this IList list, int index1, int index2) 
{
    var temp = list[index1];
    list[index1] = list[index2];
    list[index2] = temp;
}

StackExchange Code Review Q#115569, answer score: 4