A C# List Permutation Iterator

Introduction

In this article, I will present a compact, easy to use method for iterating over all permutations of a given sequence. The iteration modifies the internal order of the sequence, visiting all permutations, and eventually restoring the original order (if the enumeration process is followed through).

Using the code

The implementation of the iterator is recursive; the recursion terminal condition is when the list has only one element, in which case, it is simply returned. In the recursive case, we iterate (n) times doing a recursive call to permutate the list's first (n-1) elements, and performing a rotate-right after each iteration.

Since each full enumeration eventually restores the sequence to its original order, the rotate-right is guaranteed to position a different element at the end of the sequence each time.

public static void RotateRight(IList sequence, int count)
{
    object tmp = sequence[count-1];
    sequence.RemoveAt(count - 1);
    sequence.Insert(0, tmp);
}

public static IEnumerable<IList> Permutate(IList sequence, int count)
{
    if (count == 1) yield return sequence;
    else
    {
        for (int i = 0; i < count; i++)
        {
            foreach (var perm in Permutate(sequence, count - 1))
                yield return perm;
            RotateRight(sequence, count);
        }
    }
}

Here is how we use this code to permutate a list of integers:

static void PermutateIntegersTest()
{
    List<int> seq = new List<int>() { 1, 2, 3, 4 };
    foreach (var permu in Permutate(seq, seq.Count))
    {
        foreach (var i in permu)
            Console.Write(i.ToString() + " ");
        Console.WriteLine();
    }
}

Or to permutate a string:

using System.Linq; // For the ToList() and ToArray() extension methods.

static void PermutateStringTest()
{
    string a = "word";
    foreach (List<char> perm in Permutate(a.ToCharArray().ToList(), a.Length))
    {
        string s = new string(perm.ToArray());
        Console.Write(s + "\t");
    }
    Console.WriteLine();
}

Remember that this implementation actually modifies the order of items in the sequence, and if that is not desired, a copy of the sequence must be made before the iteration is started.

That's it, enjoy.