带字符替换的字符串组合

Question

我正试图通过我以前没有见过的场景工作，并且正在努力想出一个算法来正确实施此操作。我的问题的一部分是对正确术语的朦胧回忆。我相信我所需要的是标准“组合”问题的变体，但我很可能离开那里。

场景 给出的例子串"100"（让我们称之为x），产生的x该换出的那些0（零）个字符一个用于o（小写O）的所有组合。因此，对于"100"简单的例子，我希望这样的输出：

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

这将需要支持不同长度的字符串与不同0个字符的数字，但假设永远不会有超过5个的实例。

我有这个非常简单的算法，我的"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，我们将其视为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＃已经有适合的标准类来实现你想要的东西。 （虽然我很惊讶这么多人在这里提出递归。）

所以这是对我的问题的评论的解释或说明，而不是针对您的问题的实施建议。

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