Сочетания строк с заменой символов

Question

Я пытаюсь работать по сценарию, который я раньше не видел, и изо всех сил пытаюсь разработать алгоритм для его правильной реализации. Часть моей проблемы - это туманное воспоминание о правильной терминологии. Я считаю, что мне нужна вариация стандартной «комбинированной» проблемы, но я вполне мог бы быть там.

Сценарий приведен пример строка "100" (назовем его x), производят все комбинации x, меняющие местами одну из этих 0 (ноль) символов для o (строчного O). Таким образом, для простого примера "100", я бы ожидать, этот вывод:

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

Это нужно будет поддерживать изменения строк длины с различной номера 0 символов, но предположим, что никогда не будет более 5 экземпляров 0.

У меня есть этот очень простой алгоритм, который работает на моем образце "100" но разваливается за что больше/сложнее:

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"); 
} 

У меня есть мучительное чувство, что рекурсия может быть мой друг, но я пытаясь понять, как включить в меня условную логику.

Answer 1

Ваша догадка была правильной; рекурсия - ваш друг для этой задачи. Вот простое решение:

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

Это работает для меня:

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

Вот решение, использующее рекурсию, и ваш буфер массив:

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(); 
} 

Метод добавляет сырье вводится как первый результат. После этого мы заменяем в цикле 0 s, который мы видим как o, и вызываем наш метод обратно с этим новым входом, который будет охватывать случай нескольких 0 s.

И наконец, мы получим пару дубликатов, поэтому мы используем Distinct.

Answer 4

Здесь не требуется рекурсия, вы можете перечислить свои шаблоны и рассматривать их как двоичные числа. Например, если у вас есть три нуля в строке, вы получите:

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

Вы можете осуществить это с операторами поразрядными или путем обработки символов, которые вы хотите заменить, как одометр.

Ниже приведена реализация в C. Я не знаком с C#, и из других ответов я вижу, что у C# уже есть подходящие стандартные классы для реализации того, что вы хотите. (Хотя я удивлен, что так много peolpe предлагают рекурсию здесь.)

Так что это больше объяснение или иллюстрация моего комментария к вопросу, чем рекомендации по реализации вашей проблемы.

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 5

Я знаю, что более ранние ответы лучше. Но я не хочу, чтобы мой код терялся. :)

Мой подход к этой проблеме комбинаторики заключается в том, чтобы использовать преимущества двоичных чисел. Мой алгоритм будет выглядеть следующим образом:

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; 
}