Find all combinations in a string separated

Question

I'm trying to get all combinations in a string in c# with that idea in mind:

Given a string like foo I want to get a List<string> with the values:

f o o
fo o
foo
f oo

As you can see it's not as easy as get all the substring but get ALL the chars in a string separated by spaces.

I've tried doing something like:

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

EDIT: There are some correct answers but it's clear that any of them won't do since the strings I am working with have between 55 and 85 chars each one so that means that the best function in the answers will give me something between 2^54 and 2^84 possible combinations and that is just a bit too much.

It is clear now that find all the combinations and afterwards do something with them won't do. I'll have to drop it.

Answer 1

First things first: if the string length is n, you get 2^n strings as output. So, if you want to treat strings of length 70, you have a problem.

You can use a counter, enumerating from 0 to 2^n, and treat it as a bitwise mask: if the first bit is 1, you put a space between the first and the second char, if it's zero, you don't.

So, an unsigned long of length 64 is barely enough to treat strings of length 65.

An example implementation, without recursion (it's slightly more verbose than the other examples), but should be a lot faster than the other implementations for long inputs:

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

Probably you could get away with a bit field, but we are already in the billions of strings, so I would try to reformulate a bit the problem.

Answer 2

Here is one more recursive solution to consider:

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

For your test string produces desired result. Basically we combine first char + either space or no space + the rest of the string (without first char) recursively.

To get a list, just do Permute("foo").ToList();

For "abcde" string the result is:

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 3

A number of answers have suggested recursive solutions, which is fine. But here's a sketch of a non-recursive solution.

• Suppose your word has x letters where x is less than 64.
• Compute long n = 2^{(x - 1)}
• Make a loop where i goes from 0 to n - 1
• Decompose i into the (x-1) low bits.
• Output the first letter.
• If the first bit is set, output a space, otherwise no space.
• Output the second letter.
• If the second bit is set, output a space, otherwise no space.
• And so on.

Can you implement the method given that sketch?