12,954,672 members (67,183 online)
alternative version

#### Stats

24.1K views
16 bookmarked
Posted 14 Nov 2009

# 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

 First Prev Next
 My vote of 5 Andira Muttakim12-Jan-14 3:47 Andira Muttakim 12-Jan-14 3:47
 Permutate() arguments Seth Morris21-Nov-09 23:02 Seth Morris 21-Nov-09 23:02
 Recursion PIEBALDconsult19-Nov-09 10:32 PIEBALDconsult 19-Nov-09 10:32
 Re: Recursion George I. Birbilis31-Oct-11 4:54 George I. Birbilis 31-Oct-11 4:54
 Re: Recursion George I. Birbilis31-Oct-11 5:06 George I. Birbilis 31-Oct-11 5:06
 Re: Recursion Mr.PoorEnglish9-Oct-13 11:20 Mr.PoorEnglish 9-Oct-13 11:20
 Re: Recursion George I. Birbilis13-Mar-14 21:41 George I. Birbilis 13-Mar-14 21:41
 Re: Recursion George I. Birbilis13-Mar-14 21:49 George I. Birbilis 13-Mar-14 21:49
 Similar to C++ STL Fredrik B17-Nov-09 3:01 Fredrik B 17-Nov-09 3:01
 Needs More John Simmons / outlaw programmer15-Nov-09 1:36 John Simmons / outlaw programmer 15-Nov-09 1:36