Find all combinations in a row divided

Question

I am trying to get all combinations in a string in C # with this idea:

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

 foo fo o foo f oo 

As you can see, this is not as simple as getting the whole substring, but getting ALL characters in a string separated by spaces.

I tried to do 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 a few correct answers, but it is clear that none of them will do, since the lines I work with have between 55 and 85 characters each, so this means that the best function in the answers will give me something between 2 ^ 54 and 2 ^ 84 possible combinations, and this is too much.

Now it’s clear that I will not find all the combinations and then do something with them. I will have to give it up.

Answer 1

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

You can use a counter enumerating from 0 to 2 ^ n and treat it like a beaten mask: if the first bit is 1, you put a space between the first and second char, if it is zero, you do not.

Thus, an unsigned length of 64 is sufficient to process strings of length 65.

An example implementation without recursion (it is a bit more detailed than other examples), but should be much faster than 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(); } 

You could probably get away with a bit field, but we are already in billions of lines, so I will try to reformulate the problem a bit.

Answer 2

Here is another recursive solution:

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

The desired result is created for your test string. Basically we concatenate the first char + either a space or a space + the rest of the line (without the first char) recursively.

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

For the string "abcde" the result is:

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

Answer 3

You can do this with recursion, starting with an empty line, you call recursively add a space and without adding it, and add the 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; } } 

To type abcde , SplitString("abcde", 3) type this result:

 abc de abc de ab cde ab cd e ab c de ab cde a bcd e a bc de a bc de ab cde ab cd e abc de abcde 

Answer 4

A number of answers suggested recursive solutions, and that’s good. But here is a sketch of a non-recursive solution.

• Suppose your word has x letters, where x is less than 64.
• Calculate long n = 2 ^{(x - 1)}
• Make a loop in which I go from 0 to n - 1
• I decompose into the lower digits (x-1).
• Print the first letter.
• If the first bit is set, output a space, otherwise a space.
• Print the second letter.
• If the second bit is set, output a space, otherwise a space.
• And so on.

Can you implement a sketch-based method?

Answer 5

You can try something recursive. You start with the line, hello .

For each character, not a space, if it does not follow a space, add it to this place in the line and run the function in this line. In the first iteration, you have:

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

Repeat until all characters are followed by spaces. However, this will create duplicates.

Answer 6

What you can do is convert the string to a char array as follows:

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