13,550,152 members
alternative version

#### Stats

28.4K views
16 bookmarked
Posted 14 Nov 2009
Licenced CPOL

# A C# List Permutation Iterator

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

## About the Author

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

## Comments and Discussions

 First Prev Next
 How to find every permutations of a List object and then a specific permutation? Member 132872312-Jul-17 13:50 Member 13287231 2-Jul-17 13:50
 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 Aviad P.20-Nov-09 8:41 Aviad P. 20-Nov-09 8:41
 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
 Re: Needs More Aviad P.15-Nov-09 2:07 Aviad P. 15-Nov-09 2:07
 Last Visit: 31-Dec-99 18:00     Last Update: 21-May-18 5:49 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.