CODEWITHSUNDEEP
c#string
Miquel Coll
Miquel Coll

Reputation: 771

Find all combinations in a string separated

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.

Upvotes: 8

Views: 2420

Answers (6)

Arturo Menchaca
Arturo Menchaca

Reputation: 15982

You can do it using recursion, starting with an empty string, you call recursively adding an space and without add it, and adding current character:

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

For an input like abcde, SplitString("abcde", 3) get this output:

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

Upvotes: 3

Alberto Chiesa
Alberto Chiesa

Reputation: 7360

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.

Upvotes: 5

Eric Lippert
Eric Lippert

Reputation: 660503

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?

Upvotes: 3

Evk
Evk

Reputation: 101633

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

Upvotes: 5

user3712476
user3712476

Reputation: 138

What you could do is convert the string into a char array like this:

char characters[] = text.toCharArray()

Then in your for loop iterate through this array

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

Upvotes: -2

Samuel Lapointe
Samuel Lapointe

Reputation: 305

You could try something recursive. You start with a string, hello.

For each character that's not a space, if it's not followed by a space, add one at that location in the string and run the function on that string. On the first iteration, you have:

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

Repeat until all characters are followed by spaces. This will create duplicates though.

Upvotes: 0

Related Questions