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!
here is a straight-forward implementation, just in case you need one:
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()));
}
The answer concerning the time-complexity gave Adithya. To understand their answer you have to know that there are n! = 1*2*...*n permutations for n items. My algorithm is a proof for that (or based on the straight forward proof)
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.
Backtracking is the fastest way to go, When you want all the anagrams for a text, it means you need all the n! permutations of it. So assuming printing/generating each permutation takes O(1) atleast, your algorithm would take O(n!) anyways, hence you cant do quicker than a backtracking solution.
