{ "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 }