How to speed up this code to add chars to an string and extend it to desired length (all permutation)?
<p>I have the following code: given a string with length m, add '-' to any possible position (including between different chars of original string)  to extend it to length n. For example, given "ABC", extend it to 6. It will be "---ABC", "--A-BC", "--AB-C", "--ABC-",  ......, "AB---C", "ABC---".</p>

<pre><code>class Program
{
    // &lt;summary&gt;
    /// Grow a string to desired length with time limitation
    /// &lt;/summary&gt;
    /// &lt;param name="s"&gt;&lt;/param&gt;
    /// &lt;param name="length"&gt;&lt;/param&gt;
    /// &lt;param name="pad"&gt;&lt;/param&gt;
    /// &lt;param name="Padded"&gt;&lt;/param&gt;
    public static bool ExtendToLen(string s, int length, char pad, ref List&lt;string&gt; Padded, ref Stopwatch timer, int timeOut)
    {
        if (s.Length == length)
        {
            Padded.Add(s);
            return true;
        }
        else if (s.Length &gt; length)
        {
            return true;
        }
        else
        {
            List&lt;int&gt; pos = GetExceptPos(s, pad.ToString());
            pos.Sort();

            int count = -1;
            foreach (int p in pos)
            {
                if (timer.Elapsed.TotalSeconds &gt; timeOut)
                {
                    return false;
                }

                //Debug.WriteLine(string.Format("pos:{0}", p), "PadToLength");
                count++;

                // Pad left 
                string leftPadStr = s.Substring(0, p) + pad + s.Substring(p);
                //Debug.WriteLine(string.Format("\tLeftPadStr:{0}", leftPadStr));
                bool go = ExtendToLen(leftPadStr, length, pad, ref Padded, ref timer, timeOut);
                if (go == false) { return false; }

                // Pad right at the last pos
                if (count == pos.Count - 1)
                {
                    string rightPadStr = s + pad;
                    go = ExtendToLen(rightPadStr, length, pad, ref Padded, ref timer, timeOut);
                    if (go == false) { return false; }
                }
            }
            return true;
        }
    }

    /// &lt;summary&gt;
    /// Find indexes of elements different from target str
    /// &lt;/summary&gt;
    /// &lt;param name="str"&gt;&lt;/param&gt;
    /// &lt;param name="excludeStr"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    private static List&lt;int&gt; GetExceptPos(string str, string excludeStr)
    {
        List&lt;int&gt; allIndexes = new List&lt;int&gt;();
        for (int i = 0; i &lt; str.Length; i++)
        {
            allIndexes.Add(i);
        }

        return allIndexes.Except(str.IndexesOf(excludeStr)).ToList();
    }

    static void Main(string[] args)
    {
        string old = "ACGUA";
        List&lt;string&gt; newList = new List&lt;string&gt;();
        Stopwatch timer = new Stopwatch();
        timer.Start();
        bool isGood = ExtendToLen(old, 12, '-', ref newList, ref timer, 100);
        timer.Stop();

        foreach (string s in newList)
        {
            Console.WriteLine(s);
        }

        Console.WriteLine("Elapsed time: {0}", timer.Elapsed);
        Console.ReadLine();
    }
}

public static class ExtensionMethods
{
    /// &lt;summary&gt;
    /// Return all indeces
    /// &lt;/summary&gt;
    /// &lt;param name="haystack"&gt;&lt;/param&gt;
    /// &lt;param name="needle"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    public static IEnumerable&lt;int&gt; IndexesOf(this string haystack, string needle)
    {
        int lastIndex = 0;
        while (true)
        {
            int index = haystack.IndexOf(needle, lastIndex);
            if (index == -1)
            {
                yield break;
            }
            yield return index;
            lastIndex = index + needle.Length;
        }
    }
}
</code></pre>

<p>It runs slowly, for example, if I want to extend a string (len = 5) to 20, it runs long long long time. And the result seems to be redundant. </p>

<p>So the question is how to speed it up and remove those redundancy.</p>

<p>Any suggestion will be appreciated.</p>
