Permutation function in C#

Question

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

/// <summary>
/// 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)!
/// </summary>
/// <param name="list">The list whose permutations are needed</param>
/// <param name="startPos">The position of first element of interest in the list</param>
/// <param name="r">Number of items required in the permuted list</param>
/// <returns>An enumeration containing a permutation of the original list</returns>
public static IEnumerable<IList<T>> GetPermutations<T>(this IList<T> list, int r, int startPos = 0) {
 for (int i = startPos; i < list.Count; ++i) {
 if (r > 1) {
 list.Swap(startPos, i);
 foreach (var permute in GetPermutations(list, r - 1, startPos + 1))
 yield return new List<T>().AddRange(list[startPos].AsEnumerable(), permute);
 list.Swap(startPos, i);
 } else
 yield return new List<T>() { list[i] };
 }
}

The Utils class has the extensions used in the GetPermutations function

public static class Utils {
 public static bool Swap<T>(this IList<T> 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<T> AsEnumerable<T>(this T item) {
 yield return item;
 }
 public static List<T> AddRange<T>(this List<T> list, params IEnumerable<T>[] 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.Join(", ", permutation));

Couple of things on which I would like to get feedback are:

1. yield return in a recursive function.
2. Generation of new Lists to be yield returned, given that we will have a really large number of permutations with small increase in the input set

• Vikhram: @mjolka Added the extension code. Also, changed name from Yield to AsEnumerable
• RubberDuck: If I'm reading this correctly, you seem to be yielding a whole list, is this correct?
• Vikhram: @RubberDuck Yes, If the caller calls with say a list of 5 items requesting permutations containing 5 items, then the function will yield return a list of 5 items
• RubberDuck: Okay. I think I understand now. It seemed odd to yield a list at first, but I see what you're doing now.

Answer 1

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<T>().AddRange(list[startPos].AsEnumerable(), permute);
 list.Swap(startPos, i);
} else
 yield return new List<T>() { 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<T>().AddRange(list[startPos].AsEnumerable(), permute);
 }
 list.Swap(startPos, i);
} 
else
{
 yield return new List<T>() { 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<T>(this IList<T> list, int index1, int index2) 
{
 var temp = list[index1];
 list[index1] = list[index2];
 list[index2] = temp;
}

• Vikhram: Thanks Rick. I will read the series by Eric. The Swap function is used by other methods. A stable sorting mechanism will need a sort with check. Returning a bool helps when doing count on swap versus compare in sorting and similar algorithms to determine their efficiency.
• Rick Davin: @Vikhram Since Swap has a firm meaning of strictly swapping for so many languages, perhaps SwapIfDifferent would be a more appropriate method name.
• dfhwze: I would go for Swapify!
• t3chb0t: @dfhwze I'd go with tuples :-]