Алгоритм C #, который переупорядочивает символы в строке

Question

Я бы хотел алгоритм C #, который переупорядочивает символы в строку, которая имеет динамическую длину.Возникают проблемы с поиском, и я знаю, что он должен быть.

Алгоритм должен перераспределять элементы для формирования новых строк во всех возможных комбинациях.

Например, "cat" выдастследующее:
cat cta tca tac act atc

Answer 1

Это довольно часто задаваемый вопрос здесь.Попробуйте выполнить поиск по "перестановке", и вы найдете много хороших ответов о том, как это сделать на разных языках.

Здесь есть библиотека алгоритмов перестановки и комбинирования в C #:

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

Answer 2

Есть также операторы, которые я внес в проект MoreLinq в Google Code в ветви EvenMoreLinq. Если вам просто интересно узнать, как реализован алгоритм, выздесь можно увидеть код для Permutations<T>() .

Они разработаны так, чтобы хорошо сочетаться с LINQ и использовать как отложенную, так и потоковую оценку.Перестановки интересны, поскольку генерация всех перестановок - это операция N!, которая становится очень большой даже при небольших значениях N.В зависимости от того, как вы генерируете перестановки, вы можете (или не можете) фактически перечислять их все.

Вы также найдете алгоритмы для других комбинаторных операций ( Подмножества , PermutedSubsets , Декартовы произведения , Случайные подмножества , Срезы , Разделы и т. Д.) В той же кодовой базе.

Вот как вы можете использовать расширения MoreLinq для перестановки последовательности.Так, например, вы можете переставить строку (которая рассматривается как последовательность 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) ); 
}

Answer 3

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