How to speed up this code to add chars to an string and extend it to desired length (all permutation)?

Question

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---".

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

            int count = -1;
            foreach (int p in pos)
            {
                if (timer.Elapsed.TotalSeconds > 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;
        }
    }

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

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

    static void Main(string[] args)
    {
        string old = "ACGUA";
        List<string> newList = new List<string>();
        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
{
    /// <summary>
    /// Return all indeces
    /// </summary>
    /// <param name="haystack"></param>
    /// <param name="needle"></param>
    /// <returns></returns>
    public static IEnumerable<int> 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;
        }
    }
}

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.

So the question is how to speed it up and remove those redundancy.

Any suggestion will be appreciated.

Answer 1

This is a very rough hack and should get you started.

It basically moves the string backwards through your padding one character at a time.

static unsafe void performPaddedBubbleSort(string s, char c, int padCount, IList<string> list) {
        s = new string(c, padCount) + s;
        bool complete = false;
        int index = 0;
        int count = 0;
        fixed (char* p = s) {
            while (count < s.Length && *p == c) {
                while (index < s.Length) {
                    if (*(p + index) != c) {
                        // flip them
                        char tempChar = *(p + index);
                        if (index != 0)
                            *((p + index) - 1) = tempChar;
                        *(p + index) = c;

                        list.Add(new string(p));
                    }

                    index++;
                }
                index = 0;
                count++;
            }
        }
    }

Input of "ABC" with padding of 3 (to make it 6 chars wide) is:

--A-BC
--AB-C
--ABC-
-A-BC-
-AB-C-
-ABC--
A-BC--
AB-C--
ABC---
Elapsed time: 00:00:00.0008663

Not sure if that's exactly what you were after.. but its a start I guess. As you can see it executes in a fraction of a second.