c# - 字谜算法

Question

这是为文本生成字谜的最佳方式（最大 80 个字符长度）。示例：输入：dog 输出 dog dgo odg ogd gdo god

我只是在考虑回溯解决方案，但是如果文本更长，那将需要一段时间。

另一个想法是建立我尝试字典中的所有单词，但问题并不要求真正的单词。

有人可以指出最小时间复杂度的解决方案吗？

谢谢！

Answer 1

这是一个简单的实现，以防万一您需要：

IEnumerable<List<T>> Permutations<T>(List<T> items)
{
    if (items.Count == 0) yield return new List<T>();

    var copy = new List<T>(items);
    foreach (var i in items)
    {
        copy.Remove(i);
        foreach (var rest in Permutations(copy))
        {
            rest.Insert(0, i);
            yield return rest;
        }
        copy.Insert(0, i);
    }

}

IEnumerable<string> Anagrams(string word)
{
    return Permutations(word.ToCharArray().ToList()).Select(x => new String(x.ToArray()));
}

关于时间复杂性的答案给了 Adithya。要了解他们的答案，您必须知道有 n! = n 项的 1*2*...*n 排列。我的算法就是一个证明（或基于直接证明）

Answer 2

这个问题看起来像生成排列列表；（字谜是排列的子集，形成一个有意义的词）。嗯！可以使用 STL 的next_permutation方法按时间顺序生成排列，（每个排列的线性时间复杂度）；你可以在这里找到这个算法的讨论：http: //marknelson.us/2002/03/01/next-permutation/；STL 的算法甚至可以处理重复，在这种情况下，朴素的交换算法会失败。

有关生成排列的深入讨论，您可以查看 Donald Knuth 的TAOCP 的生成所有 Permutations部分。

Answer 3

回溯是最快的方法，当你想要一个文本的所有字谜时，这意味着你需要所有的 n! 它的排列。因此，假设打印/生成每个排列至少需要 O(1)，那么您的算法无论如何都需要 O(n!)，因此您不能比回溯解决方案做得更快。