用字符替换生成字符串组合

Question

我正在尝试解决一个我以前从未见过的场景，并且很难想出一个正确实现的算法。我的问题之一是记忆中朦胧的术语。我认为我需要的是标准“组合”问题的变体，但我可能会偏离轨道。 该场景 给定一个示例字符串"100"（我们称其为x），生成将其中一个0（零）字符替换为o（小写字母 o）的所有x组合。因此，对于简单的"100"示例，我期望得到以下输出：

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

这需要支持长度和0字符数量不同的字符串，但是假设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");
}

我有一种烦人的感觉，递归可能是我的朋友，但我在努力想出如何结合我需要的条件逻辑。

- Sven Grosen

---

你不能只是拥有一个零的位置的本地数组，然后用零和小写字母o作为二进制数字枚举替换吗？ - M Oehm

@MOehm，不太确定你的意思，请提供实现和/或更多细节。 - Sven Grosen

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

- Douglas

---

多好的解决方案！+1 - Enigmativity

@Enigmativity：谢谢！你的也很直观且功能风格 (+1) - Douglas

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

- Enigmativity

Answer 3

这里不需要递归，你可以枚举模式并将它们视为二进制数。例如，如果你的字符串中有三个零，你会得到：

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

- M Oehm

---

感谢您抽出时间发布这篇文章，我很高兴您分享了一种不同的方法。 - Sven Grosen

Answer 4

这里是一种使用递归和缓冲数组的解决方案：

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

该方法将原始输入添加为第一个结果。之后，我们在循环中用 o 替换我们看到的 0 并使用新输入调用我们的方法，这将涵盖多个 0 的情况。

最后，我们得到一些重复的内容，因此我们使用 Distinct。

- Pierre-Luc Pineault

---

很好，谢谢你对我的原始实现的体恤，并将其融入到你的代码中。 - Sven Grosen

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

- Ian CT