Jak napisać generator anagramów w czystej strukturze C# i .Net

Question

Chciałbym wygenerować wynik anagramowy danego łańcucha bez pomocy zewnętrznych bibliotek, takich jak pomocnik algorytmów Google anagram.

Przykład:

ciąg wejściowy = "GOD"

lista wyjściowa powinna wyglądać następująco jeden:

BÓG GO GD OD OG DG uczyni Bóg GDO ODG OGD DGO DOG

Answer 1

To taks okazał się niesamowite na tak wielu poziomach. Przedstawiam ci czyste rozwiązanie LINQ (ale niezbyt wydajne).

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

Odpowiedź na to pytanie będzie prawie taka sama, jak w przypadku odpowiedzi: C# Algorithm that Re-arranges Chars in a String

Answer 3

Za to, co jest warte, napisałem metody w języku Java, które zrobią to, co chcesz, a ja rozumiem, że C# jest na tyle podobny, że prawdopodobnie będziesz w stanie przeczytać kod bez większych problemów. (Składnia, to znaczy. Jeśli nie czujesz się dobrze z funkcjami rekurencyjnymi, to może ci to sprawić kłopot.) Moja nazwa użytkownika jest @Nie wymieniona na tym forum thread. Aby użyć kodu, można przechodzić przez wartości k od 1 do długości ciągu włącznie. Alternatywnie możesz wygenerować wszystkie podzbiory (odrzucając pusty zbiór), jak opisano w this thread, a następnie pobrać stąd permutacje. Innym sposobem jest napisanie funkcji kth-permutacji i użycie jej. Nie mam jednego opublikowanego online; ten, którego używam, jest nieco niechlujny i powinienem go kiedyś przepisać.

Edit: Warto wspomnieć, że napisałem metody w sposób, który wydawał się łatwy, ale bardziej efektywne byłoby użycie stosu, w ten sposób nie trzeba tworzyć mnóstwo nowych obiektów.

Answer 4

spróbować

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

po prostu skorzystać z tej metody rozszerzenie w ten sposób

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