純粋なC＃と.NETフレームワークでアナグラムジェネレータを書く方法

Question

Googleアナグラムアルゴリズムヘルパなどの外部ライブラリの助けを借りずに、指定された文字列のアナグラム出力を生成したいと思います。

例：

入力文字列= "GOD"

出力リストは、次のようになります：

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

Answer 1

を試してみてください。 私はあなたに純粋な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＃があなたがおそらく読むことができるほど似ていると理解していますコードはそれほど問題はありません。 （再帰関数に慣れていない場合は、問題が発生する可能性があります）。forum threadには、ユーザー名が@undefinedです。コードを使用するには、k値を1から文字列の長さまでループすることができます。あるいは、this threadで説明されているように、すべてのサブセットを生成することもできます（空のセットを破棄します）。もう一つの方法は、k番目の置換関数を書いてそれを使うことです。私はオンラインで投稿したものはありません。私が使っているものはちょっと乱雑ですし、いつか書き直すべきです。

編集：簡単に見える方法でメソッドを書きましたが、スタックを使用する方が効率的です。新しいオブジェクトをたくさん作成する必要はありません。

Answer 4

はtaksは非常に多くのレベルで素晴らしいことになっのはこの

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();