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.
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?
Thank you!
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.
For a indepth discussion on generating permutations, you can go through Donald Knuth's Generating all Perumutations section of TAOCP.