I'm working to understand Big O notation. As such I'm going through examples and the algorithm below generates the permutations for a given input string which contains only distinct characters. IE no duplicated or repeated characters in the input string.
My thought process was to take each character and place it at every position within any previously generated strings.
- The single character string "a" can only generate "a".
- With "ab" the first character generates "a", as above. The next character 'b' would then be added before and after it to generate "ba" and "ab".
- With "abc" this would effectively take the list generated above and repeat the same procedure placing c at position 0, 1, and 2 producing
- From "ba": "cba", "bca", "bac"
- From "ab": "cab", "acb", "abc"
- Etc...
The nested loops, foreach and for, is a big flag as to how inefficient my current implementation is, O(n * n * n) = O(n^3)\$O(n * n * n) = O(n^3)\$ if I've understood the notation correctly. How can I improve the structure to remove this nesting?
public class StringPermutation
{
public List<string> Generate(string source)
{
var list = new List<string>();
foreach (var c in source) //O(source.Length)
{
if (list.Count == 0)
{
list.Add(c.ToString());
}
else
{
var beingBuilt = new List<string>();
foreach (var tempString in list) //O(list.Count)
{
for (int i = 0; i < tempString.Length + 1; i++) //O(tempString.Length)
{
var built = tempString.Insert(i, c.ToString());
beingBuilt.Add(built);
}
}
list = beingBuilt;
}
}
return list;
}
}
