I recently chatted with a friend about the following question. Let's say that you have a string, say "sky". In how many ways can you split it into substrings. All possibilities are:
sky
sk y
s ky
s k y
Intuitively, I suspected an answer similar to $ 2^{n} $, but I didn't sit down to figure out the exact answer.
So let's solve this problem. If we start with a string which's length is N then each split can be represented in a binary form of length N. For example:
sk y = 01 1
A 1
shows that we are ending a string with the character corresponding to this 1
and a 0
shows that we're continuing a string. If we have a 0
in the beginning, we're just continuing the empty string. So in our example, 01
corresonds to sk
and the ending 1
corresponds to y
. We have to notice that a valid split always ends with 1
, because we're always ending at the end of the original word. Furthermore, all binary representations of the first N-1
characters corresponds to a possible split.
We can now see that the answer to the question is $ 2^{N-1} $.
Knowing this mapping between splits and binary numbers, we can even write some code that uses this property. It looks like this:
word = "rain"
N = len(word)
for b in range(2**(N-1)):
split = '{0:03b}'.format(b)[::-1] + '1 '
for i in range(len(word)):
split += word[i]
if b & (1 << i):
split += ' '
print split
0001 rain 1001 r ain 0101 ra in 1101 r a in 0011 rai n 1011 r ai n 0111 ra i n 1111 r a i n