c# - 如何在纯 C# 和 .Net 框架中编写字谜生成器

Question

我想在没有任何外部库（如谷歌字谜算法助手）的帮助下生成给定字符串的字谜输出。

例子：

输入字符串 = “神”

输出列表应如下所示：

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

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

对于它的价值，我用 Java 编写了可以做你想做的事情的方法，而且我理解 C# 非常相似，你可能能够轻松阅读代码。（即语法。如果您对递归函数不满意，那可能会给您带来麻烦。）我的用户名是 @undefined over on this forum thread。要使用该代码，您可以循环从 1 到字符串长度的 k 值（含）。或者，您可以按照该线程中的描述生成所有子集（丢弃空集），然后从那里获取排列。另一种方法是编写一个 kth-permutation 函数并使用它。我没有在网上发布；我使用的那个有点乱，我应该改写一下。

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

Answer 3

试试这个

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