c# - 查找分隔字符串中的所有组合

Question

考虑到这个想法，我正在尝试在 c# 中获取字符串中的所有组合:

给定一个类似 foo 的字符串我想要一个List<string>具有以下值:

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 种可能的组合，这有点太多了。

现在很清楚，找到所有的组合然后用它们做点什么是行不通的。我必须放弃它。

Answer 1

首先要注意的是:如果字符串长度为 n，您将得到 2^n 个字符串作为输出。所以，如果你想处理长度为 70 的字符串，你就有问题了。

你可以使用一个计数器，从 0 到 2^n 枚举，并将其视为按位掩码:如果第一位是 1，则放置一个空格在第一个和第二个字符之间，如果它为零，则您不这样做。

因此，长度为 64 的 unsigned long 几乎不足以处理长度为 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();
    }

也许你可以用一个位域逃脱，但我们已经有数十亿个字符串，所以我会尝试重新表述这个问题。