如何在纯C＃和.Net框架中编写anagram生成器

Question

我想生成给定字符串的anagram输出，而不需要任何外部库（例如Google字谜算法助手）的帮助。

实施例：

输入字符串= “GOD”

输出列表应该像以下各项之一：

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

Answer 1

这TAKS转作这么多层次真棒。 我为您呈现纯粹的LINQ（但不是非常高效）的解决方案。

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

答案与这里的答案几乎相同：C# Algorithm that Re-arranges Chars in a String

Answer 3

对于什么是值得的，我用Java编写了一些方法，可以做你想做的事情，而且我明白C＃是类似的，你可能会阅读代码没有太大麻烦。 （语法，也就是说，如果你对递归函数不熟悉，那可能会给你带来麻烦。）我的用户名是@undefined在这个forum thread上。要使用代码，您可以循环遍历从1到包含字符串长度的k值。或者，您可以按this thread中所述生成所有子集（丢弃空集），然后从那里获取排列。另一种方法是编写一个第k个置换函数并使用它。我没有一个在线发布;我使用的那个有点混乱，我应该在某个时候重写它。

编辑：值得一提的是，我用一种看起来很简单的方式编写了这些方法，但更高效的方法是使用堆栈，这样就不必创建大量新对象。

Answer 4

试试这个

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

然后只需使用该扩展方法这样

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