Algorithme C# qui réorganise les caractères dans une chaîne

Question

Je voudrais un algorithme C# qui réorganise les caractères dans une chaîne de longueur dynamique. J'ai du mal à en trouver un et je sais qu'il doit y en avoir un là-bas.

L'algorithme doit réaligner les éléments pour former de nouvelles chaînes dans toutes les combinaisons possibles.

Par exemple, "chat" produirait ce qui suit:
chat loi tac cta de tca atc ​​

Answer 1

C'est demandé assez souvent question ici. Essayez de faire une recherche sur "permutation" et vous trouverez beaucoup de bonnes réponses sur la façon de le faire dans différentes langues.

Il y a une bibliothèque d'algorithmes de permutation et de combinaison en C# ici:

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

Answer 2

Il y a aussi les opérateurs que je contribué à la MoreLinq project on Google Code dans la branche EvenMoreLinq. Si vous êtes simplement curieux de savoir comment l'algorithme est implémenté, vous pouvez voir le code for Permutations<T>() here.

Ils sont conçus pour se fondre bien avec LINQ, et utilisent à la fois l'évaluation en différé et en continu. Les permutations sont intéressantes, car la génération de toutes les permutations est une opération N! ... qui devient très grande même pour de petites valeurs de N. Selon la façon dont vous générez des permutations, vous pouvez (ou ne pouvez pas) les énumérer tous.

Vous trouverez également des algorithmes pour d'autres opérations combinatoires (Subsets, PermutedSubsets, Cartesian Products, Random Subsets, Slices, Partitions, etc.) dans la même base de code.

Voici comment vous pouvez utiliser les extensions MoreLinq pour permuter une séquence. Ainsi, par exemple, vous pouvez permuter une chaîne (qui est traitée comme une séquence de char s) comme suit:

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