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

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

这是另一个需要考虑的递归解决方案:

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

对于您的测试字符串产生所需的结果 基本上我们递归地组合第一个char +空格或没有空格+字符串的其余部分(没有第一个字符).

要获得一个列表,就这样做 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

Answer 2

首先要做的事情是：如果字符串长度为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();
    }

可能你可以使用位域，但我们已经在数十亿个字符串中，所以我会尝试重新表述这个问题。