con sostituzione caratteri

Question

Sto provando a elaborare uno scenario che non ho mai visto prima e sto cercando di trovare un algoritmo per implementarlo correttamente. Parte del mio problema è un vago ricordo della terminologia corretta. Credo che quello di cui ho bisogno sia una variazione del problema della "combinazione" standard, ma potrei essere fuori.

Scenario Dato una stringa esempio "100" (che chiameremo x), producono tutte le combinazioni di x che scambieranno una delle dette 0 caratteri (zero) per un o (minuscola o). Così, per il semplice esempio di "100", mi sarei aspettato questa uscita:

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

Ciò avrebbe bisogno di sostenere varia stringhe di lunghezza con diversi numeri di 0 caratteri, ma supponiamo che non ci saranno mai più di 5 istanze di 0.

ho questo algoritmo molto semplice che funziona per il mio campione di "100" ma cade a pezzi per qualcosa di più/più complicato:

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

Ho una fastidiosa sensazione che la ricorsione potrebbe essere il mio amico qui, ma io sono lottando per capire come incorporare la logica condizionale di cui ho bisogno qui.

Answer 1

La tua ipotesi era corretta; la ricorsione è il tuo amico per questa sfida. Qui è una soluzione semplice:

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

questo funziona per 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

Ecco una soluzione utilizzando la ricorsione, e la matrice del buffer:

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

Il metodo aggiunge l'ingresso crudo come il primo risultato. Successivamente, sostituiamo in loop il 0 s che vediamo come o e richiamiamo il nostro metodo con quel nuovo input, che coprirà il caso di più 0 s.

Infine, ci ritroviamo con un paio di duplicati, quindi utilizziamo Distinct.

Answer 4

Non hai bisogno di ricorsione qui, puoi enumerare i tuoi modelli e trattarli come numeri binari. Ad esempio, se si dispone di tre zeri nella stringa, si ottiene:

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

È possibile implementare che con gli operatori bit per bit o trattando i caratteri che si desidera sostituire come un contachilometri.

Di seguito è un'implementazione in C. Non ho familiarità con C# e dalle altre risposte vedo che C# ha già classi standard adatte per implementare quello che vuoi. (Anche se sono sorpreso che così tante persone propongano la ricorsione qui.)

Quindi questa è una spiegazione o illustrazione del mio commento alla domanda piuttosto che un consiglio di implementazione per il tuo problema.

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

So che le risposte precedenti sono migliori. Ma non voglio che il mio codice vada sprecato. :)

Il mio approccio per questo problema di combinatoria sarebbe quello di sfruttare il funzionamento dei numeri binari. Il mio algoritmo potrebbe essere il seguente:

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