这是产生字谜一个文本（最多80个字符的长度）的最佳方式。 例： 输入：狗 输出狗DGO总干事办公室缺氧缺糖GDO神

Which is the best way of generating anagrams for a text(maximum 80 characters length). Example: Input: dog output dog dgo odg ogd gdo god

我只是在想一个回溯的解决方案，但是这将需要一段时间，如果文本的长度。

I'm only thinking of a backtracking solution, but that will take a while if the text is longer.

另一个想法是BULDING我线索在字典中的所有单词，但这个问题不要求实际的话。

Another thought is bulding i trie for all words in dictionary, but the problem doesn't ask for real words.

有人能指出一个最短的时间复杂度的解决方案？

Can somebody point out a minimum time complexity solution?

感谢您！

推荐答案

这个问题看起来像产生排列列表; （字谜是置换，从而形成一个有意义的词的子集）。 N！置换可以按时间顺序使用STL的 next_permutation 的方法，（在线性时间内产生每置换的复杂性）;你可以在这里找到该算法的讨论： http://marknelson.us/2002/ 3月1日/下一置换/ ; STL的算法甚至可以处理重复和幼稚交换算法失败在这种情况下

The question looks like generating the list of permutations; (Anagrams are a subset of permutations, which form a meaningful word). n! Permutations can be generated in chronological order using the approach of STL's next_permutation, (linear time complexity per permutation); You can find the discussion of this algorithm here: http://marknelson.us/2002/03/01/next-permutation/ ; STL's algorithm can even handle duplicates and the naive swap algorithm fails in this case.

有关生成排列一个深入讨论，你可以通过高德纳公司的生成TAOCP所有Perumutations 部分。

For a indepth discussion on generating permutations, you can go through Donald Knuth's Generating all Perumutations section of TAOCP.