在一个由字符串组成的序列中找到所有的组合

Question

我正在尝试在C#中获取字符串的所有组合，具体思路如下：

给定一个字符串，如"foo"，我想获取一个值为List的列表，其中包含以下内容：

f o o
fo o
foo
f oo

正如您所看到的那样，它不仅仅是获取所有子字符串，而是获取由空格分隔的字符串中的所有字符。

我尝试过类似以下的操作：

List<string> result = new List<string>();
string text = "foo";
for (int i = 1; i < foo.Lenght; i++) 
{
    //I'm stucked --> everything I think is too stupid and I don't know how to procede or not fast enough. I'm really stuck.
}

编辑： 有一些正确的答案，但很明显它们都不适用于我正在处理的字符串，因为每个字符串都有55到85个字符，这意味着最好的答案函数将给我2^54到2^84个可能的组合，这太多了。

现在清楚了，找到所有组合，然后对它们进行操作是行不通的。我必须放弃它。

- Miquel Coll

---

不需要进行排列组合吗？ 我的意思是 ofo 是有效还是无效结果？另外，fo、f、o 和重复项（第二个 o）呢，它们是有效还是无效的？ - Khalil Khalaf

没有任何排列组合和子串都是有效的。我放在那里的例子就是全部内容。 - Miquel Coll

递归函数。 - Khalil Khalaf

是的，我知道我必须使用递归来完成它，但由于今天我过得非常辛苦，我的头脑不太清晰，虽然我相信用递归应该很容易实现（但每次尝试时我都卡住了）。 - Miquel Coll

真的，但我们通常不会只是因为你今天心情不好就写代码。如果你今天过得不开心，就明天再看吧。 - BugFinder

Answer 1

这里有一种递归解决方案可以考虑：

private static IEnumerable<string> Permute(string target) {
   if (target.Length <= 1) {
        yield return target;
        yield break;
    }
    var c = target[0];
    foreach (var rest in Permute(target.Remove(0, 1))) {
        yield return c + rest;
        yield return c + " " + rest;
    }
}

对于你的测试字符串产生了期望的结果。基本上，我们递归地组合第一个字符+空格或没有空格+剩余的字符串（不包括第一个字符）。

要获取列表，只需执行Permute("foo").ToList();

对于字符串“abcde”，结果如下：

abcde
a bcde
ab cde
a b cde
abc de
a bc de
ab c de
a b c de
abcd e
a bcd e
ab cd e
a b cd e
abc d e
a bc d e
ab c d e
a b c d e

- Evk

Answer 2

首先，如果字符串长度为n，则输出2^n个字符串。因此，如果要处理长度为70的字符串，则会遇到问题。

您可以使用计数器，从0枚举到2^n，并将其视为位掩码：如果第一位为1，则在第一个字符和第二个字符之间放置一个空格；如果为零，则不需要。

因此，长度为64的无符号长整型仅足以处理长度为65的字符串。

以下是一个示例实现，不使用递归（比其他示例略微冗长），但对于长输入应该比其他实现快得多。

    public IEnumerable<string> GetPartitionedStrings(string s)
    {
        if (s == null) yield break;

        if (s == "")
        {
            yield return "";
            yield break;
        }

        if (s.Length > 63) throw new ArgumentOutOfRangeException("String too long...");

        var arr = s.ToCharArray();
        for(ulong i = 0, maxI = 1UL << (s.Length - 1); i < maxI; i++)
        {
            yield return PutSpaces(arr, i);
        }
    }

    public string PutSpaces(char[] arr, ulong spacesPositions)
    {
        var sb = new StringBuilder(arr.Length * 2);
        sb.Append(arr[0]);

        ulong l = 1;
        for (int i = 1; i < arr.Length; i++, l <<= 1)
        {
            if ((spacesPositions & l) != 0UL) sb.Append(" ");

            sb.Append(arr[i]);
        }

        return sb.ToString();
    }

可能您可以使用位域，但由于我们已经有数十亿个字符串，所以我建议稍微改变一下问题的表述。

- Alberto Chiesa

---

谢谢你的回答，尽管我最终不得不放弃它。（我已经更新了我的问题并解释了我的意思） - Miquel Coll

Answer 3

一些答案提出了递归解决方案，这是可以的。但这里提供了一个非递归解决方案的概述。

• 假设您的单词有x个字母，其中x小于64。
• 计算long n = 2^{(x - 1)}
• 创建一个循环，其中i从0到n-1
• 将i分解为(x-1)个低位。
• 输出第一个字母。
• 如果第一位被设置，输出空格，否则不输出空格。
• 输出第二个字母。
• 如果第二位被设置，输出空格，否则不输出空格。
• 依此类推。

你能够实现这个方法吗？

- Eric Lippert

---

多少来说，这正是我的答案算法。 - Alberto Chiesa

Answer 4

您可以使用递归来实现，从一个空字符串开始，您可以递归调用添加一个空格和不添加空格，并且添加当前字符：

static IEnumerable<string> SplitString(string s, int max)
{
    return SplitString(s, 0, max, max);
}

private static IEnumerable<string> SplitString(string s, int idx, int available, int maxLength)
{
    if (idx == s.Length) yield return string.Empty;
    else
    {
        if (available > 0)
            foreach (var item in SplitString(s, idx + 1, available - 1, maxLength))
                yield return s[idx] + item;

        if (idx > 0)
            foreach (var item in SplitString(s, idx + 1, maxLength - 1, maxLength))
                yield return " " + s[idx] + item;
    }
}

对于像abcde这样的输入，SplitString("abcde", 3)会得到以下输出结果：

abc de
abc d e
ab cde
ab cd e
ab c de
ab c d e
a bcd e
a bc de
a bc d e
a b cde
a b cd e
a b c de
a b c d e

- Arturo Menchaca

---

我真的很喜欢那种方法；但是在这种情况下，我正在处理长度在50到70个字符之间的字符串，这意味着有很多排列。如果我能够省略重复，并对每个子字符串设置一个长度限制（例如，我不需要任何长度大于6的子字符串的排列），我真的可以加快速度。 - Miquel Coll

Answer 5

你可以尝试使用递归的方法。首先，你有一个字符串hello。

对于每个不是空格的字符，如果它后面没有空格，则在该位置添加一个空格并在该字符串上运行函数。在第一次迭代中，你会得到：

• h ello
• he llo
• hel lo
• hell o
• hello

重复此过程，直到所有字符后面都跟着空格。这样会产生重复的结果。

- Samuel Lapointe

---

这不是一个答案，而只是一个提示。 - Khalil Khalaf

对不起，我是新手。如果我只发布代码，那么这算回答吗？ - Samuel Lapointe

如果它完全解决了原始问题/帖子中提出的问题，那么它被认为是一个答案。 - Khalil Khalaf

请参考以上答案，它们展示了直接和明确的修复方法，而不仅仅是像我在评论中和你在这里所做的那样提供指导或追踪修复过程。 - Khalil Khalaf

Answer 6

你可以将字符串转换为字符数组，像这样： char characters[] = text.toCharArray() 然后在for循环中遍历该数组。

for (int i = 1; i < foo.Lenght; i++) 
{
    System.out.println(characters[i]);
}

- user3712476

---

首先，它只是打印出每个字符，并没有创建一个带有添加空格的原始字符串列表。其次，那是Java代码，不是C#。 - juharr

嗯，你是对的，我没意识到这是一个C#的讨论串。无论如何，他需要一些代码方向。为了让他的代码正常工作，他可以将字符串转换为数组，然后再解决其余的问题。 - user3712476