String Combinations With Character Replacement

Question

I am trying to work through a scenario I haven't seen before and am struggling to come up with an algorithm to implement this properly. Part of my problem is a hazy recollection of the proper terminology. I believe what I am needing is a variation of the standard "combination" problem, but I could well be off there.

The Scenario Given an example string "100" (let's call it x), produce all combinations of x that swap out one of those 0 (zero) characters for a o (lower-case o). So, for the simple example of "100", I would expect this output:

• "100"
• "10o"
• "1o0"
• "1oo"

This would need to support varying length strings with varying numbers of 0 characters, but assume there would never be more than 5 instances of 0.

I have this very simple algorithm that works for my sample of "100" but falls apart for anything longer/more complicated:

public IEnumerable<string> Combinations(string input)
{
    char[] buffer = new char[input.Length];

    for(int i = 0; i != buffer.Length; ++i)
    {
        buffer[i] = input[i];
    }

    //return the original input
    yield return new string(buffer);

    //look for 0's and replace them
    for(int i = 0; i != buffer.Length; ++i)
    {
        if (input[i] == '0')
        {
            buffer[i] = 'o';
            yield return new string(buffer);
            buffer[i] = '0';
        }
    }

    //handle the replace-all scenario
    yield return input.Replace("0", "o");
}

I have a nagging feeling that recursion could be my friend here, but I am struggling to figure out how to incorporate the conditional logic I need here.

Answer 1

Your guess was correct; recursion is your friend for this challenge. Here is a simple solution:

public static IEnumerable<string> Combinations(string input)
{
    int firstZero = input.IndexOf('0');   // Get index of first '0'
    if (firstZero == -1)      // Base case: no further combinations
        return new string[] { input };

    string prefix = input.Substring(0, firstZero);    // Substring preceding '0'
    string suffix = input.Substring(firstZero + 1);   // Substring succeeding '0'
    // e.g. Suppose input was "fr0d00"
    //      Prefix is "fr"; suffix is "d00"

    // Recursion: Generate all combinations of suffix
    // e.g. "d00", "d0o", "do0", "doo"
    var recursiveCombinations = Combinations(suffix);

    // Return sequence in which each string is a concatenation of the
    // prefix, either '0' or 'o', and one of the recursively-found suffixes
    return 
        from chr in "0o"  // char sequence equivalent to: new [] { '0', 'o' }
        from recSuffix in recursiveCombinations
        select prefix + chr + recSuffix;                                    
}

Answer 2

This works for me:

public IEnumerable<string> Combinations(string input)
{
    var head = input[0] == '0' //Do I have a `0`?
        ? new [] { "0", "o" } //If so output both `"0"` & `"o"`
        : new [] { input[0].ToString() }; //Otherwise output the current character

    var tails = input.Length > 1 //Is there any more string?
        ? Combinations(input.Substring(1)) //Yes, recursively compute
        : new[] { "" }; //Otherwise, output empty string

    //Now, join it up and return
    return
        from h in head
        from t in tails
        select h + t;
}

Answer 3

You don't need recursion here, you can enumerate your patterns and treat them as binary numbers. For example, if you have three zeros in your string, you get:

0    000    ....0..0....0...
1    001    ....0..0....o...
2    010    ....0..o....0...
3    011    ....0..o....o...
4    100    ....o..0....0...
5    101    ....o..0....o...
6    110    ....o..o....0...
7    111    ....o..o....o...

You can implement that with bitwise operators or by treating the chars that you want to replace like an odometer.

Below is an implementation in C. I'm not familiar with C# and from the other answers I see that C# already has suitable standard classes to implement what you want. (Although I'm surprised that so many peolpe propose recursion here.)

So this is more an explanation or illustration of my comment to the question than an implementation advice for your problem.

int binrep(char str[])
{
    int zero[40];       // indices of zeros
    int nzero = 0;      // number of zeros in string
    int ncombo = 1;     // number of result strings
    int i, j;

    for (i = 0; str[i]; i++) {
        if (str[i] == '0') {
            zero[nzero++] = i;
            ncombo <<= 1;
        }
    }

    for (i = 0; i < ncombo; i++) {
        for (j = 0; j < nzero; j++) {
            str[zero[j]] = ((i >> j) & 1) ? 'o' : '0';
        }

        printf("%s\n", str);    // should yield here
    }

    return ncombo;
}

Answer 4

Here's a solution using recursion, and your buffer array:

private static void Main(string[] args)
{
    var a = Combinations("100");
    var b = Combinations("10000");
}

public static IEnumerable<string> Combinations(string input)
{
    var combinations = new List<string>();

    combinations.Add(input);

    for (int i = 0; i < input.Length; i++)
    {
        char[] buffer= input.ToArray();
        if (buffer[i] == '0')
        {
            buffer[i] = 'o';
            combinations.Add(new string(buffer));
            combinations = combinations.Concat(Combinations(new string(buffer))).ToList();
        }
    }

    return combinations.Distinct();
}

The method adds the raw input as the first result. After that, we replace in a loop the 0s we see as a o and call our method back with that new input, which will cover the case of multiple 0s.

Finally, we end up with a couple duplicates, so we use Distinct.

Answer 5

I know that the earlier answers are better. But I don't want my code to go to waste. :)

My approach for this combinatorics problem would be to take advantage of how binary numbers work. My algorithm would be as follows:

List<string> ZeroCombiner(string str)
{
    // Get number of zeros.
    var n = str.Count(c => c == '0');
    var limit = (int)Math.Pow(2, n);

    // Create strings of '0' and 'o' based on binary numbers from 0 to 2^n.
    var binaryStrings = new List<string>();
    for (int i = 0; i < limit; ++i )
    {
        binaryStrings.Add(Binary(i, n + 1));
    }

    // Replace each zero with respect to each binary string.
    var result = new List<string>();
    foreach (var binaryString in binaryStrings)
    {
        var zeroCounter = 0;
        var combinedString = string.Empty;
        for (int i = 0; i < str.Length; ++i )
        {
            if (str[i] == '0')
            {
                combinedString += binaryString[zeroCounter];
                ++zeroCounter;
            }
            else
                combinedString += str[i];
        }
        result.Add(combinedString);
    }

    return result;
}

string Binary(int i, int n)
{
    string result = string.Empty;
    while (n != 0)
    {
        result = result + (i % 2 == 0 ? '0' : 'o');
        i = i / 2;
        --n;
    }
    return result;
}