Split string

[Won]

Hi!

I would like to know, how could I split a string in all possible way?

For example: 123456789

It's easy to write the code, to split into two.
1 23456789
12 3456789
123 456789
1234 56789
12345 6789
123456 789
1234567 89
12345678 9

And it's also easy to write a code to split into 3.
But, I can't figour it out, how could I split in all possible way? (into 1,2,3,...n)
The problem is, that I don't know, how long is the input.

Have anybody any idea?

Thanks!

[MiiNiPaa]

What do you need? Calculate amount of splits or actually generate all possible splits?

[Won]

Generate all of them.
The number of all splits is 2^(n-1) where n is the lenght of the string.

[MiiNiPaa]

Each split of string with length n can be represented by n-1 binary digits where nth digit is denoting if there should be split between nth and n+1th string symbol.

number:  0 0 1 0 0 0 0 1
string: 1 2 3|4 5 6 7 8|9

As you can see from example number 00100001b is denoting split 123 45678 9.
As there 2^n-1 possible binaly numbers with lenght of n-1, there exactly that number of splits.
So you just need to create function which will give you a split based on number, generate all possible binary numbers and call that function with each number.

[Won]

Thats a cool idea!! Thank you!!

[andywestken]

how could I split in all possible way?

A naive approach would be just to either insert a space or not?

(a) start
1234

(b) insert a space before second char, or not
1234
1 234

(c) insert a space before third char, or not
1234
12 34
1 234
1 2 34

(d) insert a space before fourth char, or not
1234
123 4
12 34
12 3 4
1 234
1 23 4
1 2 34
1 2 3 4

(Trivial to code with recursion...)

Andy

[owCjz8AR]

#include<iostream>
#include<string>
using namespace std;
void main()
{
string st = "123456789";
int count = 1;
for (int i = 0; i < st.length() -1; i++)
{
for (int j = 0; j < st.length(); j++)
{
if (count== j)
{
cout << " ";
cout << st[j];
}
else
cout << st[j];
}
cout << endl;
count++;
}
}

[Won]

Recursion is a good idea, but I would like to store them in a 2 dimensional vector.
If the the lenght of the input is n than I will have max. n pieces. And the number of all combination is 2^(n-1).

So I need to store them in a n×2^(n-1) matrix. But n isn't a constant, so I have to use vectors.

I would like to use the substr() function to split the string.

Any idea?

[MiiNiPaa]

set the beginning character to 0.
iterate over "split" array. As soon as you encounter 1, remember its position n. If no 1 is found, set n to size of split array;
set the end character to n;
extract substring [0,n];
if we still not reach the end of split array:
set beginning character to end character + 1; 
continue iterating through split array (go to 2nd line)

[andywestken]

Any idea?

Yes!

But I think the next step is for you to have a go at coding some sort of solution!

Andy :-)

[Won]

Yes, but my problem is, that I would like to seperate the substrings.
For example:

1 2 3456789
1 23 456789
1 234 56789
1 2345 6789
1 23456 789
1 234567 89
1 2345678 9
12 3 456789
12 34 56789
...
...
...
123456 7 89
123456 78 9
1234567 8 9

So this is a matrix. I want to use a 2D vector, not to put them in one.

[Won]

Yes Andy, you are right! :)
I'm trying it for a while. I just would like to get ideas. I don't give up!

Edit: I coded the solution what MiiNiPaa mentioned, but I think it takes more time to generate all the binary numbers and then split with the binary.

[andywestken]

Well, try coding a function that does just the first split.

Then one which does the first and second.

Then one which does the first three splits; at that point you should start to see how to make it recursive.

Andy

[Won]

OK, I'll try.

[MiiNiPaa]

Example of doing it my way: http://ideone.com/fBUAcx

[Won]

Thank you very much MiiNiPaa!! It works perfectly!

In some version of MingGW the to_string() function doesn't works because of a bug.

But it can be easily fixed:

namespace patch
{
    template < typename T > std::string to_string( const T& n )
    {
        std::ostringstream stm ;
        stm << n ;
        return stm.str() ;
    }
}

And instead of:

std::to_string();

use

patch::to_string();