13,259,771 members (52,406 online)
alternative version

#### Stats

25.9K views
16 bookmarked
Posted 14 Nov 2009

# A C# List Permutation Iterator

, 14 Nov 2009
 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...

 First Prev Next
 How to find every permutations of a List object and then a specific permutation? Member 132872312-Jul-17 14:50 Member 13287231 2-Jul-17 14:50
 My vote of 5 Andira Muttakim12-Jan-14 4:47 Andira Muttakim 12-Jan-14 4:47
 Permutate() arguments Seth Morris22-Nov-09 0:02 Seth Morris 22-Nov-09 0:02
 Personally, I like the simplicity of the recursive implementation. It's easy to understand and easy to maintain. It might take a few more cycles to run, but those cycles are not a big deal in many real-world cases. My only suggestion is that passing the count in on the original call seems inelegant and error prone. An extension method to the interface can make it clearer:
public static class ListPermutation {       // Put the static Permutate and RotateRight methods in this class as well       public static IEnumerable Permutations(this IList list)       {             return Permutate(list, list.Count);       } }
then call with
foreach (var permu in seq.Permutations())
I'd probably make two extensions so I could have one that makes a copy rather than modify the order. And, of course, you'd want to use the technique on generic lists instead of type-unsafe ones in real code.
 Recursion PIEBALDconsult19-Nov-09 11:32 PIEBALDconsult 19-Nov-09 11:32
 Re: Recursion George I. Birbilis31-Oct-11 5:54 George I. Birbilis 31-Oct-11 5:54
 Re: Recursion George I. Birbilis31-Oct-11 6:06 George I. Birbilis 31-Oct-11 6:06
 Re: Recursion Mr.PoorEnglish9-Oct-13 12:20 Mr.PoorEnglish 9-Oct-13 12:20
 Re: Recursion George I. Birbilis13-Mar-14 22:41 George I. Birbilis 13-Mar-14 22:41
 Re: Recursion George I. Birbilis13-Mar-14 22:49 George I. Birbilis 13-Mar-14 22:49
 Similar to C++ STL Fredrik B17-Nov-09 4:01 Fredrik B 17-Nov-09 4:01
 Needs More John Simmons / outlaw programmer15-Nov-09 2:36 John Simmons / outlaw programmer 15-Nov-09 2:36