重新排列字符串中字符的C#算法

这是一个相当常见的问题。试着在“排列”上搜索一下,你会发现很多关于如何用各种语言进行排列的好答案。

在C语言中有一个排列和组合算法库#这里:

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

MoreLinq project on Google Code 在 EvenMoreLinq 分支机构。 code for Permutations<T>() here .

它们被设计成与LINQ很好地融合,并使用延迟和流式计算。置换是一个有趣的问题,因为生成所有置换是一个复杂的过程 N! 操作。。。即使是很小的 N . 根据生成置换的方式,您可能(也可能不)能够实际枚举所有置换。

您还可以找到其他组合运算的算法( Subsets PermutedSubsets Cartesian Products , Random Subsets , Slices Partitions ,等等)在同一个代码库中。

char

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

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