# 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

/// <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))
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)
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
• @mjolka Added the extension code. Also, changed name from Yield to AsEnumerable Commented Jan 2, 2016 at 12:16
• If I'm reading this correctly, you seem to be yielding a whole list, is this correct? Commented Jan 2, 2016 at 12:52
• @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 Commented Jan 2, 2016 at 12:55
• Okay. I think I understand now. It seemed odd to yield a list at first, but I see what you're doing now. Commented Jan 2, 2016 at 12:57

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.

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

• 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. Commented Jan 2, 2016 at 16:39
• @Vikhram Since Swap has a firm meaning of strictly swapping for so many languages, perhaps SwapIfDifferent would be a more appropriate method name. Commented Jan 2, 2016 at 18:27
• I would go for Swapify! Commented Jun 20, 2019 at 5:44
• @dfhwze I'd go with tuples :-] Commented Jun 20, 2019 at 16:48