anagram算法

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

我只想到一个回溯解决方案，但如果文本更长，那将需要一段时间。

另一个想法是为字典中的所有单词建立起来，但问题不是要求真正的单词。

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

谢谢！

Answer 1

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

有关生成排列的深入讨论，您可以通过Donald Knuth的TAOCP的Generate all Perumutations部分。

Answer 2

这是一个直接的实现，以防万一你需要一个：

IEnumerable> Permutations(List items) { if (items.Count == 0) yield return new List(); var copy = new List(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 Anagrams(string word) { return Permutations(word.ToCharArray().ToList()).Select(x => new String(x.ToArray())); } 

关于时间复杂性的答案给了Adithya。 要了解他们的答案你必须知道有n！ n项的= 1 * 2 * … * n排列。 我的算法certificate了这一点（或基于直接certificate）

Answer 3

回溯是最快的方式，当你想要文本的所有字谜时，就意味着你需要所有的n！ 它的排列。 所以假设打印/生成每个排列至少需要O（1），你的算法无论如何都需要O（n！），因此你不能比回溯解决方案更快。