CODEWITHSUNDEEP
c#algorithmstringpermutation
Jeff LaFay
Jeff LaFay

Reputation: 13350

C# Algorithm that Re-arranges Chars in a String

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

Upvotes: 3

Views: 1404

Answers (3)

mbadeveloper
mbadeveloper

Reputation: 1270

static void Main(string[] args)
{
    Console.WriteLine("Enter String:");
    string inputString = Console.ReadLine();
    Console.WriteLine();
    List<string> lstAnagrams = new List<string>();
    int numAnagram = 1;

    permute(inputString.ToCharArray(), 0, inputString.Length - 1, lstAnagrams);
    foreach(string anagram in lstAnagrams)
    {
        Console.WriteLine(numAnagram.ToString() + " " + anagram);
        numAnagram++;
    }

    Console.ReadKey();
}

static void permute(char[] word, int start, int end, List<string> lstAnagrams)
{
    if (start == end)
        lstAnagrams.Add(string.Join("", word));
    else
    {
        for (int position = start; position <= end; position++)
        {
            swap(ref word[start], ref word[position]);
            permute(word, start + 1, end,lstAnagrams);
            swap(ref word[start], ref word[position]);
        }
    }
}

static void swap(ref char a, ref char b)
{
    char tmp;
    tmp = a;
    a = b;
    b = tmp;
}

Upvotes: -1

LBushkin
LBushkin

Reputation: 131646

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

Upvotes: 6

Eric Lippert
Eric Lippert

Reputation: 659956

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

Upvotes: 10

Related Questions