Character Combinations of Strings

Question

I am trying to work on a scenario that I have not seen before, and I am struggling to develop an algorithm for its correct implementation. Part of my problem is a hazy memory of the right terminology. I believe that I need a variation of the standard “combined” problem, but I could very well be there.

Scenario With the sample string "100" (call her x ), create all combinations of x that change one of these characters 0 (zero) to o (lowercase o). So, for a simple "100" example "100" I would expect this output:

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

This should support variable length strings with different character numbers 0 , but suppose there will never be more than 5 instances of 0 .

I have this very simple algorithm that works for my "100" sample, but falls apart into something more complex:

 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 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 stunning feeling that recursion can be my friend here, but I'm struggling to figure out how to include conditional logic here.

Answer 1

Your guess was right; recursion is your friend for this task. 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' // eg Suppose input was "fr0d00" // Prefix is "fr"; suffix is "d00" // Recursion: Generate all combinations of suffix // eg "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

Here you do not need recursion, you can list your patterns and treat them as binary numbers. For example, if your line has three zeros, 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 this with bitwise operators or by treating the characters you want to replace, like an odometer.

The following is an implementation in C. I am not familiar with C #, and from other answers I can see that C # already has the appropriate standard classes for implementing what you want. (Although I am surprised that so many peolpe offer recursion here.)

So, this is more explanation or illustration of my comment on the question than recommendations for implementing 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

This uses a recursive solution 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 original input as the first result. After that, we will replace 0 as o in the loop and return our method back with this new input, which will cover the case of several 0 s.

Finally, we get a couple of duplicates, so we use Distinct .

Answer 5

I know that earlier answers are better. But I do not want my code to get lost. :)

My approach to this combinatorics problem will be to take advantage of binary numbers. 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; }