Wie schreibe ich einen Anagramm-Generator in reinem C# und. NET-Framework

Question

Ich möchte Anagramm-Ausgabe einer bestimmten Zeichenfolge ohne die Hilfe von externen Bibliotheken wie Google Anagramm-Algorithmen-Helfer generieren.

Beispiel:

Eingangs string = "GOD"

Ausgabeliste wie folgt aussehen sollte:

GOD GO GD OD OG DG DO GOD GDO ODG OGD DGO DOG

Answer 1

diese Art und Weise verwenden, die taks genial auf so vielen Ebenen erwiesen. Ich präsentiere Ihnen eine reine LINQ (aber nicht sehr effizient) Lösung.

static class Program 
    { 
     static void Main(string[] args) 
     { 
      var res = "cat".Anagrams(); 

      foreach (var anagram in res) 
       Console.WriteLine(anagram.MergeToStr()); 
     } 

     static IEnumerable<IEnumerable<T>> Anagrams<T>(this IEnumerable<T> collection) where T: IComparable<T> 
     { 
      var total = collection.Count(); 

      // provided str "cat" get all subsets c, a, ca, at, etc (really nonefficient) 
      var subsets = collection.Permutations() 
       .SelectMany(c => Enumerable.Range(1, total).Select(i => c.Take(i))) 
       .Distinct(new CollectionComparer<T>()); 

      return subsets; 
     } 

     public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> collection) 
     { 
      return collection.Count() > 1 
       ? 
        from ch in collection 
        let set = new[] { ch } 
        from permutation in collection.Except(set).Permutations() 
        select set.Union(permutation) 
       : 
        new[] { collection }; 
     } 

     public static string MergeToStr(this IEnumerable<char> chars) 
     { 
      return new string(chars.ToArray()); 
     } 

    }// class 

    // cause Distinct implementation is shit 
    public class CollectionComparer<T> : IEqualityComparer<IEnumerable<T>> where T: IComparable<T> 
    { 
     Dictionary<IEnumerable<T>, int> dict = new Dictionary<IEnumerable<T>, int>(); 

     public bool Equals(IEnumerable<T> x, IEnumerable<T> y) 
     { 
      if (x.Count() != y.Count()) 
       return false; 
      return x.Zip(y, (xi, yi) => xi.Equals(yi)).All(compareResult => compareResult); 
     } 

     public int GetHashCode(IEnumerable<T> obj) 
     { 
      var inDict = dict.Keys.FirstOrDefault(k => Equals(k, obj)); 
      if (inDict != null) 
       return dict[inDict]; 
      else 
      { 
       int n = dict.Count; 
       dict[obj] = n; 
       return n; 
      } 
     } 
    }// class 

Answer 2

Die Antwort darauf ist fast die gleiche wie die Antworten hier: C# Algorithm that Re-arranges Chars in a String

Answer 3

Für was es wert ist, schrieb ich Methoden in Java, die tun, was Sie wollen, und ich verstehe C# ist ähnlich genug, dass Sie wahrscheinlich lesen können der Code ohne viel Ärger. (Die Syntax, das heißt. Wenn Sie nicht mit rekursiven Funktionen vertraut sind, dann könnte das Ihnen Probleme bereiten.) Mein Benutzername ist @undefined über auf diesem forum thread. Um den Code zu verwenden, könnten Sie k-Werte von 1 bis zur Länge Ihrer Zeichenkette einschleifen. Alternativ könnten Sie alle Untermengen erzeugen (die leere Menge verwerfen), wie in this thread beschrieben, und dann die Permutationen von dort abrufen. Eine andere Möglichkeit besteht darin, eine k-te-Permutationsfunktion zu schreiben und diese zu verwenden. Ich habe keine online gestellt; Die eine, die ich benutze, ist ein bisschen unordentlich und ich sollte es irgendwann neu schreiben.

Bearbeiten: Erwähnenswert, dass ich die Methoden in einer Weise geschrieben, die einfach schien, aber effizienter wäre, einen Stapel zu verwenden, auf diese Weise müssen Sie Tonnen von neuen Objekten nicht erstellen.

Answer 4

versuchen diese

public static IEnumerable<string> Permutations(this string text) 
{ 
    return PermutationsImpl(string.Empty, text); 
} 

private static IEnumerable<string> PermutationsImpl(string start, string text) 
{ 
    if (text.Length <= 1) 
     yield return start + text; 
    else 
    { 
     for (int i = 0; i < text.Length; i++) 
     { 
      text = text[i] + 
        text.Substring(0, i) + 
        text.Substring(i + 1); 
      foreach (var s in PermutationsImpl(start + 
       text[0], text.Substring(1))) 
       yield return s; 
     } 
    } 
} 

dann einfach diese Erweiterung Methode

string text = "CAT"; 
List<string> perms = text.Permutations().ToList();