12,690,839 members (31,701 online)
alternative version

23.1K views
16 bookmarked
Posted

# A C# List Permutation Iterator

, 14 Nov 2009 CPOL
 Rate this:
An iterator in C# which iterates over all permutations of a given IList.

## 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.

## Share

 Software Developer (Senior) Israel
Software developer since 1984, currently specializing in C# and .NET.

## You may also be interested in...

 Pro

 View All Threads First Prev Next
 Similar to C++ STL Fredrik B17-Nov-09 4:01 Fredrik B 17-Nov-09 4:01
 Last Visit: 31-Dec-99 19:00     Last Update: 16-Jan-17 20:25 Refresh 1