字符串组合与字符替换 [英] String Combinations With Character Replacement

问题描述

我想通过我以前没有见过的情景工作，很努力拿出一个算法来正确地实现这一点。我的问题的一部分是正确的术语朦胧的回忆。我相信我所需要的是标准的结合问题的变化，但我很可能会关闭在那里。

I am trying to work through a scenario I haven't seen before and am struggling to come up with an algorithm to implement this properly. Part of my problem is a hazy recollection of the proper terminology. I believe what I am needing is a variation of the standard "combination" problem, but I could well be off there.

场景
给出一个例子字符串100（姑且称之为 X ），产生<$ C的所有组合$ C> X ：交换了其中的一个 0 （零） 0 （小写O）。因此，对于简单的例子100，我希望这样的输出：

The Scenario Given an example string "100" (let's call it x), produce all combinations of x that swap out one of those 0 (zero) characters for a o (lower-case o). So, for the simple example of "100", I would expect this output:

• 100


• 10°


• 1O0


• 1OO

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

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

This would need to support varying length strings with varying numbers of 0 characters, but assume there would never be more than 5 instances of 0.

我有这个非常简单的算法，对于工作我的样本100但分崩离析为更长的东西/更复杂的：

I have this very simple algorithm that works for my sample of "100" but falls apart for anything longer/more complicated:

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

我有一种挥之不去的感觉，递归可能是我的朋友在这里，但我。努力弄清楚如何把条件逻辑我需要在这里

I have a nagging feeling that recursion could be my friend here, but I am struggling to figure out how to incorporate the conditional logic I need here.

推荐答案

您的猜测是正确的;递归是你的朋友对这一挑战。这里有一个简单的解决方案：

Your guess was correct; recursion is your friend for this challenge. Here is a simple solution:

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

这篇关于字符串组合与字符替换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！