c# - 查找带和不带连字符的单词的所有可能组合

Question

对于其中可能包含零个或多个连字符的字符串，我需要提取所有包含和不包含连字符的不同可能性。

例如，字符串“A-B”将导致“A-B”和“AB”(两种可能性)。

字符串“A-B-C”将产生“A-B-C”、“AB-C”、“A-BC”和“ABC”(四种可能)。

字符串“A-B-C-D”将产生“A-B-C-D”、“AB-C-D”、“A-BC-D”、“A-B-CD”、“AB-CD”、“ABC-D”、“A-” BCD”和“ABCD”(八种可能)。

……等等，等等

我尝试了一些嵌套循环，但一直无法获得接近预期的结果。我怀疑我需要一些递归的东西，除非有一些我忽略的简单解决方案。

注意。这是为了构建一个 SQL 查询(遗憾的是 SQL Server 没有 MySQL 的 REGEXP 模式匹配)。

这是我正在进行的一项尝试。如果我递归执行此操作，这可能会起作用。

string keyword = "A-B-C-D";

List<int> hyphens = new List<int>();

int pos = keyword.IndexOf('-');
while (pos != -1)
{
    hyphens.Add(pos);
    pos = keyword.IndexOf('-', pos + 1);
}

for (int i = 0; i < hyphens.Count(); i++)
{
    string result = keyword.Substring(0, hyphens[i]) + keyword.Substring(hyphens[i] + 1);

    Response.Write("<p>" + result);
}

A B C D 是不同长度的单词。

Answer 1

查看您的示例案例。你注意到一个模式了吗？

• 1 个连字符有 2 种可能性。
• 2 个连字符有 4 种可能性。
• 3 个连字符有 8 种可能性。

可能性的数量是 2ⁿ。

这实际上是指数增长，所以如果字符串中的连字符太多，很快就无法全部打印出来。 (仅 30 个连字符就有超过 10 亿种组合!)

也就是说，对于较少数量的连字符，生成一个列表可能会很有趣。为此，您可以将每个连字符视为二进制数中的一个位。如果该位为 1，则存在连字符，否则不存在。所以这提出了一个相当简单的解决方案:

1. 在连字符上拆分原始字符串
2. 令 n = 连字符数
3. 从 2ⁿ - 1 到 0 计数。将此计数器视为位掩码。
4. 对于每个计数，从第一部分开始构建一个字符串。
5. 按顺序将每个剩余部分连接到字符串，仅当设置了位掩码中的相应位时才在前面加上连字符。
6. 将结果字符串添加到输出并继续，直到计数器用完。

翻译成我们的代码:

public static IEnumerable<string> EnumerateHyphenatedStrings(string s)
{
    string[] parts = s.Split('-');
    int n = parts.Length - 1;
    if (n > 30) throw new Exception("too many hyphens");
    for (int m = (1 << n) - 1; m >= 0; m--)
    {
        StringBuilder sb = new StringBuilder(parts[0]);
        for (int i = 1; i <= n; i++)
        {
            if ((m & (1 << (i - 1))) > 0) sb.Append('-');
            sb.Append(parts[i]);
        }
        yield return sb.ToString();
    }
}

fiddle :https://dotnetfiddle.net/ne3N8f