{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# In how many ways can you split a string into all possible substrings?\n",
"\n",
"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:\n",
"\n",
"```\n",
"sky\n",
"sk y\n",
"s ky\n",
"s k y\n",
"```\n",
"\n",
"Intuitively, I suspected an answer similar to $ 2^{n} $, but I didn't sit down to figure out the exact answer.\n",
"\n",
"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:\n",
"\n",
"```\n",
"sk y = 01 1\n",
"```\n",
"\n",
"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.\n",
"\n",
"We can now see that the answer to the question is $ 2^{N-1} $.\n",
"\n",
"Knowing this mapping between splits and binary numbers, we can even write some code that uses this property. It looks like this:\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0001 rain\n",
"1001 r ain\n",
"0101 ra in\n",
"1101 r a in\n",
"0011 rai n\n",
"1011 r ai n\n",
"0111 ra i n\n",
"1111 r a i n\n"
]
}
],
"source": [
"word = \"rain\"\n",
"N = len(word)\n",
"\n",
"for b in range(2**(N-1)):\n",
" split = '{0:03b}'.format(b)[::-1] + '1 '\n",
" for i in range(len(word)):\n",
" split += word[i]\n",
" if b & (1 << i):\n",
" split += ' '\n",
" print split"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.11"
}
},
"nbformat": 4,
"nbformat_minor": 2
}