C# Algorithm that Re-arranges Chars in a String

Question

I would like a C# algorithm that re-arranges the chars in a string that is dynamic in length. Having trouble finding one and I know there has to be one out there.

The algorithm has to realign elements to form new strings in all possible combinations.

For instance, "cat" would produce the following:
cat cta tca tac act atc

Answer 1

This is a fairly frequently asked question here. Try doing a search on "permutation" and you'll find a lot of good answers about how to do this in various languages.

There is a library of permutation and combination algorithms in C# here:

http://www.codeproject.com/KB/recipes/Combinatorics.aspx

Answer 2

This may help.

Answer 3

There are also the operators I contributed to the MoreLinq project on Google Code in the EvenMoreLinq branch. If you're just curious about how the algorithm is implemented, you can see the code for Permutations<T>() here.

They are designed to blend well with LINQ, and use both deferred and streaming evaluation. Permutations is an interesting one, since generating all permutations is a N! operation ... which becomes very large for even small values of N. Depending on how you generate permutations, you may (or may not) be able to actually enumerate them all.

You'll also find algorithms for other combinatoric operations (Subsets, PermutedSubsets, Cartesian Products, Random Subsets, Slices, Partitions, etc) in that same codebase.

Here's how you can use the MoreLinq extensions to permute a sequence. So for instance, you could permute a string (which is treated as a sequence of chars) as follows:

using MoreLinq;

string input = "cat";
var permutations = input.Permutations();

foreach( var permutation in permutations )
{
    // 'permutation' is a char[] here, so convert back to a string
    Console.WriteLine( new string(permutation) ); 
}