Click here to Skip to main content
13,259,771 members (52,406 online)
Click here to Skip to main content
Add your own
alternative version


16 bookmarked
Posted 14 Nov 2009

A C# List Permutation Iterator

, 14 Nov 2009
Rate this:
Please Sign up or sign in to vote.
An iterator in C# which iterates over all permutations of a given IList.


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;
        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() + " ");

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");

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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

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

You may also be interested in...

Comments and Discussions

QuestionHow to find every permutations of a List<Vector2> object and then a specific permutation? Pin
Member 132872312-Jul-17 14:50
memberMember 132872312-Jul-17 14:50 
GeneralMy vote of 5 Pin
Andira Muttakim12-Jan-14 4:47
memberAndira Muttakim12-Jan-14 4:47 
GeneralPermutate() arguments Pin
Seth Morris22-Nov-09 0:02
memberSeth Morris22-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:

<pre>public static class ListPermutation
      // Put the static Permutate and RotateRight methods in this class as well
      public static IEnumerable<IList> Permutations(this IList list)
            return Permutate(list, list.Count);

then call with
<pre>      foreach (var permu in seq.Permutations())</pre>

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.
GeneralRecursion Pin
PIEBALDconsult19-Nov-09 11:32
memberPIEBALDconsult19-Nov-09 11:32 
GeneralRe: Recursion Pin
Aviad P.20-Nov-09 9:41
memberAviad P.20-Nov-09 9:41 
GeneralRe: Recursion Pin
George I. Birbilis31-Oct-11 5:54
memberGeorge I. Birbilis31-Oct-11 5:54 
GeneralRe: Recursion Pin
George I. Birbilis31-Oct-11 6:06
memberGeorge I. Birbilis31-Oct-11 6:06 
GeneralRe: Recursion Pin
Mr.PoorEnglish9-Oct-13 12:20
memberMr.PoorEnglish9-Oct-13 12:20 
GeneralRe: Recursion Pin
George I. Birbilis13-Mar-14 22:41
memberGeorge I. Birbilis13-Mar-14 22:41 
GeneralRe: Recursion Pin
George I. Birbilis13-Mar-14 22:49
memberGeorge I. Birbilis13-Mar-14 22:49 
GeneralSimilar to C++ STL Pin
Fredrik B17-Nov-09 4:01
memberFredrik B17-Nov-09 4:01 
GeneralNeeds More Pin
John Simmons / outlaw programmer15-Nov-09 2:36
mvpJohn Simmons / outlaw programmer15-Nov-09 2:36 
GeneralRe: Needs More Pin
Aviad P.15-Nov-09 3:07
memberAviad P.15-Nov-09 3:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171114.1 | Last Updated 15 Nov 2009
Article Copyright 2009 by Aviad P.
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid