12,395,388 members (69,701 online)
alternative version

21.9K 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...

 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
 The recursive version can overflow if there are many items in the list. Ideally you need a lexicographic algorighm (Djikstra from what I've read). A non-recursive version would be f(List)->List and give you the NEXT pemutation back, then would pass the result to f to get the next value etc. When finished would return Null or throw exception (prefer Null). Could also work on the List param directly (don't mean ByRef, ByVal passing is fine, can alter items of the list then) which is useful if you have a huge list and return a boolean to say if it did permute the list or if there are no more permutations (in the order the algorighm counts the permutations). Ideally each call would do minimal changes (a transposition or more) of items, except maybe for the first call which would reorder items to make the list the 1st in the algorithm counting order. So you could have a paged listview like that and show results on demand. I'd also like a separate call (hoping a very faster one) to return just the count of permutations (maybe via Polya theory?) An issue is also if you count EQUAL (not =, but equal in object content) items many times (suppose you have a list [a,a,a,a,a], does it have just 1 permutation or do you treat it as [?,?,?,?,?], that is conent agnostic counting of the permutations?). Again Polya theory can help by defining the equivalence transforms and then listing/counting the non-equivalent instances Computer & Informatics Engineer Microsoft MVP J# 2004-2010 Borland Spirit of Delphi 2001 QuickTime, QTVR, Delphi VCL, ActiveX, COM, .NET, Robotics http://zoomicon.com http://zoomicon.wordpress.com
 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