Method to generate a List containing permutation of an input string 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)\$ if I've understood the notation correctly. How can I improve the structure to remove this nesting?

public class StringPermutation
{
    public List&lt;string&gt; Generate(string source)
    {
        var list = new List&lt;string&gt;();
        foreach (var c in source) //O(source.Length)
        {
            if (list.Count == 0)
            {
                list.Add(c.ToString());
            }
            else
            {
                var beingBuilt = new List&lt;string&gt;();
                foreach (var tempString in list) //O(list.Count)
                {
                    for (int i = 0; i &lt; tempString.Length + 1; i++) //O(tempString.Length)
                    {
                        var built = tempString.Insert(i, c.ToString());
                        beingBuilt.Add(built);
                    }
                }

                list = beingBuilt;
            }
        }

        return list;
    }
}
Before making some general remarks about the C# code, I would like to explain why the complexity of this algorithm is already optimal, even though it is not the standard approach to tackle this problem. 

Complexity Analysis

As already stated in a comment, your complexity analysis is way off. The problem is your assumption that the loop over list only multiplies the runtime by the length \$n\$ of the source. However, the list grows each iteration of the outer loop.

How complex is it really?

To determine the real complexity, we have to have a closer look at what happens inside the outer loop. By design, the list will contain all permutations of the first \$(k-1)\$ elements when the \$k^{th}\$ iteration starts. Each element of list has length \$(k-1)\$, accordingly, and there are \$(k-1)!\$ of them. So, in the \$k^{th}\$ iteration, we generate \$((k-1)+1)\cdot(k-1)! = k!\$ new permutations. Since we have to save a new string of length \$k\$ each time, which takes time \$k\$, up to a constant offset and multiplication with a constant, for each iteration we need \$k\cdot k!\$ character operations. This leaves us with a total runtime of \$\sum_{k=1}^nk\cdot k!\$.

It is not really straight forward that this is smaller than a multiple of \$n\cdot n!\$, i.e. that the complexity of the algorithm is \$O(n\cdot n!)\$. As a first step, we can reduce the problem a bit using the fact that \$k\leq n\$.

\$\sum_{k=1}^nk\cdot k! \leq n \cdot \sum_{k=1}^nk! = n \cdot n! \cdot \sum_{k=1}^n\frac{k!}{n!}\$

Now, let us make a convenient approximation for the items in the sum on the rhs, using that \$ \frac{1}{m} \leq \frac{1}{l} \$ for \$ m \geq l \$.

\$ \frac{k!}{n!} = \frac{1}{\prod_{m=k+1}^n m} \leq \frac{1}{\prod_{m=k+1}^n (m-k)} = \frac{1}{\prod_{l=1}^{n-k}l} = \frac{1}{(n-k)!} \$

This approximation allows us to get on the track of the argument used in the complexity analysis of the approach to generate permutations more often used in literature, namely generating all prefixes of permutations of the string of increasing length via recursion.

\$ \sum_{k=1}^n\frac{k!}{n!} \leq \sum_{k=1}^n\frac{1}{(n-k)!} = \sum_{m=0}^{n-1}\frac{1}{m!} \leq \sum_{m=0}^{\infty}\frac{1}{m!} = e\$

In the second equation, we used the the substitution \$m=n-k\$, which turns the summation order around. Moreover, for the last argument, one has to know that the exponential function is defined as function \$e^x = \sum_{n=0}^\infty \frac{x^n}{n!}\$.

The argument about convergence to a constant is similar in nature to that in the analysis of the average insert time into a dynamic array, which is often presented in CS classes. That argument uses a different series, though.

Why is this optimal?

To see that a \$O(n\cdot n!)\$ is optimal is not too hard. We know that there are \$n!\$ many permutations and that we have to generate a string of length \$n\$ for each, which each takes a number of character operations proportional to the length. So, we end up with at least \$n\cdot n!\$ character operations.

General Remarks

To be honest, I cannot find a lot to improve here regarding the coding style. One could separate the contents of the outer loop into a separate private function Permutations(List&lt;string&gt; permutationsOfPrefix, char nextCharacter), but I think it is equally as valid to keep the algorithm contained in one single method, especially since it is not very long. I also do not think that using LINQ here would improve the readability.

One point I think could be improved is there, though, the naming of variables. 'list' is a very generic name. I think permutationsOfPrefix would be more fitting. Accordingly, tempString could be permutation or permutationOfPrefix and beingBuilt could be permutationsWithNextCharacter. That would describe a bit better what is going on. Similarly, the i in the for loop could be named insertionIndex.    

Another possible improvement is to explicitly check whether the input string is null or empty at the start, to return an empty list in this case and, otherwise, to initialize list with the first character contained. This would allow to remove the if-else-statement inside the outer loop. However, it would require to iterate over source.Drop(1) in the outer loop.