帶字符替換的字符串組合

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