कैरेक्टर रिप्लेसमेंट के साथ स्ट्रिंग संयोजन

Question

मैं ऐसे परिदृश्य के माध्यम से काम करने की कोशिश कर रहा हूं जिसे मैंने पहले नहीं देखा है और इसे ठीक से कार्यान्वित करने के लिए एल्गोरिदम के साथ आने के लिए संघर्ष कर रहा हूं। मेरी समस्या का हिस्सा उचित शब्दावली का एक आलसी याद है। मेरा मानना ​​है कि मुझे जो चाहिए वह मानक "संयोजन" समस्या का एक भिन्नता है, लेकिन मैं वहां से अच्छी तरह से हो सकता था।

परिदृश्य एक उदाहरण स्ट्रिंग "100", कि एक o (लोअर केस ओ) के लिए उन 0 (शून्य) पात्रों में से एक बाहर स्वैप x के सभी संयोजनों का उत्पादन (यह x कॉल) को देखते हुए।

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

यह अलग-अलग लंबाई तार अलग समर्थन करने के लिए की आवश्यकता होगी: तो, "100" के सरल उदाहरण के लिए, मैं इस उत्पादन उम्मीद करेंगे 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 एस के मामले को शामिल किया जाएगा।

अंत में, हम दो डुप्लिकेट के साथ समाप्त होते हैं, इसलिए हम 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... 

आप बिटवाइज़ ऑपरेटर्स के साथ या वर्ण है कि आप एक ओडोमीटर तरह बदलना चाहते हैं इलाज है कि लागू कर सकते हैं।

नीचे सी में एक कार्यान्वयन है। मैं सी # से परिचित नहीं हूं और अन्य उत्तरों से मैं देखता हूं कि सी # में पहले से ही उपयुक्त मानक कक्षाएं हैं जो आप चाहते हैं। (हालांकि मुझे आश्चर्य है कि इतने सारे 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; 
}